Insertion_sort_ 구현

insertion sort 의 정렬방법

insertion sort 구현도중 오늘 공부한 virtual keyword, override 키워드 사용하여 클래스로 구현완료.

정적클래스 사용으로 소멸자부분 추가 구현 필요없을것으로 판단하여 미구현하였음.

Header.h

---

#include<cstdio>

#include<cstdlib>

#include<ctime>

#define INDEX_ARRAY 8

//define 으로 배열의 최대 인덱스값 지정.

// insertion-sort 로 정렬하여라.

class DataSturct {

// 자료구조 이름을 가진 클래스 생성.

protected:

// 보호접근자로 상속된 클래스 접근가능하도록 작성

int dataArray[INDEX_ARRAY];

// 배열의 정보

void swap(int&a, int& b) {

int temp = a;

a = b;

b = temp;

}

// 정렬에 필요한 swap 함수 protected 내 정의

int arrayIndex = 0;

// inputData에 배열의 최대값을 check 할 변수 생성.

public:

// 데이터값 입력을 위한 함수.

void inputData(int data) {

if (arrayIndex >= INDEX_ARRAY) {

printf("arrayIsFULL!\n");

}

//현재 배열인덱스가 배열의 최대 인덱스값과 같거나 클경우 배열은 가득찬상태임.

//그러므로 사용자에게 메시지를 출력하여 더이항 값을 넣지못하도록 안내메시지 출력

else {

dataArray[arrayIndex] = data;

arrayIndex++;

}

// 그렇지않다면 값을 넣어라.

}

virtual void insertionSort() = 0;

//overide로 InsertionSort 상속진행.

void printArray() {

for (int i = 0; i < INDEX_ARRAY; i++) {

printf("[%d] ", dataArray[i]);

}

printf("\n");

}

};

class Sort : public DataSturct {

public:

// insertion sort의 개념.

// 1. 좌측과 우측 두개의 값을 비교한다 

// 2. 우측값이 좌측값보다 작을경우 swap 한다. 좌측으로이동 그러나 값이 우측이 클경우 이동하지않음.

// 3. swap후 1번으로 이동하여 계속 진행한다 하지만 값이 이동될필요가 없을경우 4번진행

// 4. 다음값으로 이동하여 1번부터 진행

virtual void insertionSort() override  {

for (int i = 1; i < INDEX_ARRAY; i++) {

for (int k = i; k > 0; k--) {

if (dataArray[k] < dataArray[k - 1]) {

swap(dataArray[k], dataArray[k - 1]);

}

}

}

}

};

Source.cpp

---

#include"Header.h"

int main() {

Sort a1;

//a1 인스턴스 생성.

a1.inputData(10);

a1.inputData(3);

a1.inputData(7);

a1.inputData(5);

a1.inputData(15);

a1.inputData(1);

a1.inputData(4);

a1.inputData(17);

// a1.inputData(88);

//arrayIndex Max = 8 이므로 인덱스값 초과시 메시지 출력

a1.printArray();

// print 하는 함수 

a1.insertionSort();

// insertionSort 진행하는 함수.

a1.printArray();

fgetc(stdin);

return 0;

}