상세 컨텐츠

본문 제목

Insertion_sort_ 구현

개발생활/DataStructure

by 한국인맛집 2017. 5. 25. 00:35

본문

반응형



insertion sort 의 정렬방법


Insertion-sort-example-300px.gif



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;

}

반응형

'개발생활 > DataStructure' 카테고리의 다른 글

자료구조 기초  (0) 2017.12.06
Binary Search Tree 구현. 자료구조 공부  (31) 2017.06.08
Class 사용 Queue 구현  (0) 2017.05.25
[Data_Struct] Stack 구현  (0) 2017.05.23
Linked_list [data_struct]  (31) 2017.05.22

관련글 더보기