정렬 - 선택, 버블, 삽입, 병합, 힙, 퀵

1. 선택 정렬(Selection sort) -> O(n^2)

 

에 대해 i = 0 k= n -1, min 값을 찾아 i 자리와 swap 

마지막 인덱스까지 돌면서 비교 

 

코드 : 

void selectionSort(int arr[], int size){
int minIndex;
int i, j;
for(int i = 0; i < size - 1; i++){
    minIndex = i;
    for(int j = i + 1; j < size; j++){
        if(arr[j] < arr[minIndex]){
            minIndex = j;
            }
    }
    swqp(&arr[i], &arr[minIndex]);
}

---

2. 버블 정렬(Bubble sort) -> O(n^2)

 

현재 배열 요소와 다음 배열 요소를 비교하고 교환하는 식의 정렬

 

코드 : 

void bubbleSort(int arr[], int size){
    int i, j;
    for(i = size - 1; i > 0; i--){
        for(j = 0; j < i; j++){
            if(arr[j] < arr[j + 1]{
                swap(&arr[j], &arr[j + 1]);
            }
        }
    }

 

---

3. 삽입 정렬(Insertion sort) -> O(n^2), 최적의 경우 O(n) (정렬된 경우) 

 

 

key를 알맞은 자리에 삽입하는 것이다. 

key 보다 큰 값은 하나씩 밀어버리고 key 보다 작은 값을 만나면 뒷자리에 삽입한다. 

key인 8을 맨 앞에 삽입하고 i 가 하나 증가하여 비교합니다. key는 1이 된다.

 

코드 :

void insertionSort(int arr[], int size){
    int i, j, key;
    for(i = 1; i < size; i++){
        key = arr[i];
        j = i - 1;
        while(j >= 0 && arr[j] > key){
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    } 
}

---

4. 병합 정렬 (Merge sort)

두 가지 작업으로 구성된다.

 

1. 분할

void mergeSort(int arr[], int left, int right){
    if (left == right) return; // 하나의 원소만 남으면 return 
    int mid;
    
    mid = (left + right ) /2;
    mergeSort(arr, left, right);
    mergeSort(arr, mid + 1, right);
}

2. 병합

void merge(int arr[], int left, int right){
    int L, R, k, a;
    int mid = (left + right) / 2;
    L = left;
    R = mid + 1;
    k = left;
    while(L <= mid && R <= right){
        tmp[k++] = arr[L] < arr[R] ? arr[L++] : arr[R++];
    }
    
    if(L > mid){
        for(a = R; a <= rifht; a++){
            tmp[k++] = arr[a];
        }
    else{
        for( a = L; a <= mid; a++){
            tmp[k++] = arr[a];
        }
    }
    for(a = left; a <=right; a++){
        arr[a] = tmp[a];
    }

 

왼쪽 배열, 오른쪽 배열 하나라도 전부 반복이 되었다면 탈출한다.

 

 

왼쪽 부분 배열과 오른쪽 부분 배열 원소를 비교해서 더 작은 값이 tmp로 복사된다. 

 

< 전체 코드 >

void mergeSort(int arr[], int left, int right) {
  if (left == right) return;
  int mid;
  mid = (left + right) / 2;
  mergeSort(arr, left, mid); 
  mergeSort(arr, mid + 1, right); 
  merge(arr, left, right); 
}

 

---

5. 힙 정렬 (heap sort)

• 최소 힙(min heap) ?

자식은 자신보다 크기만 하면 된다. 왼쪽 오른쪽 따질 필요 없이 자식으로 넣기만 하면 된다. 

완전 이진 트리 규칙 그대로 적용해야 한다. 

힙을 배열 형태로 구현한다.

 

자식은 leftChild = parent*2, rightChild = parent*2+1

부모는 parent = child/2

로 하면 된다. 

 

heap struct pointer 코드 :

typedef struct heap {
  int arr[MAX_N];
  int size;
} heap;

 

insert 시 O(nlog(n))

void insert(heap * hp, int data){
  int here = ++hp-> size;
  while((here!=1) && (data < hp->arr[here/2]){
    hp->arr[here] = hp->arr[here/2];
    here/=2;
  }
  hp->arr[here] = data;
}

 

delete 시 O(nlog(n))

int delete(heap *hp){
  if(hp -> size == 0) return -1;
  int ret = hp -> arr[1];
  hp->arr[1] = hp->arr[hp->size--];
  int parent = 1;
  int child;
  while (1) {
    child = parent * 2;
    if (child + 1 <= hp->size && hp->arr[child]>hp->arr[child + 1]){
    	child++;
    }
    if (child>hp->size||hp->arr[child] > hp->arr[parent]) break;
    swap(&hp->arr[parent], &hp->arr[child]);
    parent = child;
  }
	return ret;
}

 

 

heap을 만드는 함수 -> heapify

void heapify(int arr[], int here, int size){
  int left = here * 2 + 1;
  int right = here * 2 + 2;
  int max = here;
  if(left < size && arr[left] > arr[max]){
  	max = left;
  }
  if(right < size && arr[right] > arr[max]){
  	max = right;
  }
  if(max != here){
  	swap(&arr[here], &arr[max]);
  	heapify(arr, max, size);
  }
}

 

 

이렇게 하면 최대 힙은 아니다. 4가 가장 큰 값이 아니므로 

따라서 자식 노드를 가진 노드가 있다면 heapify를 역순으로 호출하는 것이다. -> buildHeap

void buildHeap(int arr[], int size) {
    int i,j;
    for (i = size / 2 - 1; i >= 0; i--) { //자식 가진 부모노드에 해대 
        heapify(arr, i, size);
        for (j = 0; j < size; j++)
            printf("%d ", arr[j]);
        printf("\n\n");
    }
}

 

heap Sort 전체 코드 :

void heapSort(int arr[],int size) {
    int treeSize;
    buildHeap(arr, size);
    for (treeSize = size - 1; treeSize >= 0; treeSize--) {
        swap(&arr[0], &arr[treeSize]);
        heapify(arr, 0,treeSize);
    }
}

---

6. 퀵정렬 (quick sort) -> O(nlogn)

 

pivot을 기준으로 비대칭 분할 

pivot 보다 작은 그룹과 큰 그룹으로 분할한다. 원소가 1개가 되어 더이상 분할 할 수 없을 대까지 반복하고 분할 완료 시 정렬도 완료가 된다.

 

코드 :

void quickSort(int arr, int left, int right){
	int pivot, i, j, temp;
    if(left < right){
    i = left;
    j = right + 1;
    pivot = arrp[left];
    
    do {
    	do { i++; } while (arr[i] < pivot);
        do { j--; } while (arr[i] > pivot);
        if(i < j){
        	temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    } while( i< j);
    temp = arr[left];
    arr[left] = arr[j];
    arr[j] = temp;
    
    quickSort(arr, left, j -i);
    quickSort(arr, j + 1, right);
    }
}