정렬 알고리즘(퀵 정렬, 삽입 정렬, 계수 정렬)

삽입 정렬 알고리즘

#include <stdio.h>

#include <string.h>

void insertionSort(int DataSet[], int Length )

{

int i = 0;

int j = 0;

int value = 0;

for (i = 1; i < Length; i++){

if (DataSet[i - 1] <= DataSet[i]) { continue; }

value = DataSet[i];

for (j = 0; j < i; j++){

if (DataSet[j]>value){

//배열에서 한칸씩 값 옮기기

memmove(&DataSet[j + 1], &DataSet[j], sizeof(DataSet[0]) * (i - j));

DataSet[j] = value;

break;

}

}

}

}

int main()

{

int DataSet[] = { 6, 4, 2, 3, 1, 5 };

int Length = sizeof DataSet / sizeof DataSet[0];

int i = 0;

insertionSort(DataSet, Length);

for (int i = 0; i < Length; i++)

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

printf("\n");

return 0;

}

삽입정렬은 데이터 집합을 순회하면서 정렬이 필요한 요소를 뽑아내서 이를 적당한 곳에 삽입해 나가는 알고리즘.

1. 정렬대상은 왼쪽부터 선택해 나가며, 범위는 처음 2개에서 알고리즘 반복 횟수가 늘어날때마다 1씩 증가하여 n-1번 실행.

2. 정렬대상의 가장 오른쪽 요소가 가장 큰 값이라면 정렬할 필요가 없으므로 범위를 바로 한칸 늘림, 가장 큰 값이 아니라면 적절한 위치를 찾아서 넣어야 한다.

3. 적절한 위치를 찾았다면, 정렬 대상 내에서 삽입할 값보다 큰 값을 갖는 모든 요소를 한 자리씩 오른쪽으로 이동시키고, 새로 생긴 빈자리에 삽입.

4. 정렬이 완료될 때까지 1~4반복

시간복잡도 n^2로 버블정렬과 동일하지만, 삽입정렬은 어느정도 데이터가 정렬되어 있는 경우 버블정렬보다 비교연산을 적게 한다.

따라서 버블정렬보다는 삽입정렬이 더 나은 성능을 보인다.

퀵 정렬 알고리즘

//퀵정렬은 Divide and Conquer에 기반한 알고리즘

#include <stdio.h>

void Swap(int* A, int * B)

{

int Temp = *A;

*A = *B;

*B = Temp;

}

int Partition(int DataSet[], int left, int right)

{

int first = left;

int pivot = DataSet[first];

//DataSet[left]값이 pivot보다 작으면 left값 차례로 증가

//DataSet[right]값이 pivot보다 크다면 right값 차례로 감소

//left >= right되면, left위치와 pivot의 값, 위치 바꾸기

++left;

while (left <= right)

{

while (DataSet[left] <= pivot && left < right){

left++;

}

while (DataSet[right] >= pivot && left <= right){

right--;

}

if (left < right){

Swap(&DataSet[left], &DataSet[right]);

}

else{

break;

}

}

Swap(&DataSet[first], &DataSet[right]);

return right; //배열에서 pivot값이 들어간 위치 반환,, 해당 위치를 기준으로 파티션을 나누기 위하여

}

void QuickSort(int DataSet[], int left, int right)

{

if (left < right){

int Index = Partition(DataSet, left, right);

//퀵소트 재귀 호출 

QuickSort(DataSet, left, Index - 1);

QuickSort(DataSet, Index + 1, right);

}

}

int main()

{

int DataSet[] = { 6, 4, 2, 3, 1, 5 };

int Length = sizeof DataSet / sizeof DataSet[0];

int i = 0;

QuickSort(DataSet, 0, Length - 1);

for (int i = 0; i < Length; i++)

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

printf("\n");

return 0;

}

1. 데이터 집합 내에서 임의의 기준 요소를 선택하고, 기준 요소보다 작은 요소는 순서에 관계없이 무조건 기존 요소의 왼쪽에, 큰 값은 오른쪽에 위치시킨다.

2. 1에서 나눠진 데이터 집합을 다시 임의의 기준 요소를 선택하여 1을 반복한다.

3. 1과 2의 과정을 더 이상 데이터 집합을 나눌 수 없을 때까지 반복하면 정렬된 데이터 집합을 얻게 된다.

데이터가 미리 정렬되어 있거나 역순으로 정렬되어 있는 경우에는 최악의 성능을 보인다.

데이터가 이리저리 흩어져 있는 경우에는 최고의 성능을 보인다.

최악인 경우 : n^2

평균 : 1.39nlog2^n

최선 : nlog2^n

축약한 퀵정렬 알고리즘

#include<stdio.h>

int arr[9] = { 0, 1, 7, 2, 5, 9, 5, 4, 8 };

void quick(int left, int right) {

int i, j, k;

float s, t;

if (left < right) {

s = arr[(left + right) / 2];

i = right + 1;

j = left - 1;

while (1) {

while (arr[--i] > s);

while (arr[++j] < s);

if (i <= j) break;

t = arr[i]; arr[i] = arr[j]; arr[j] = t;

}

quick(left, j - 1);

quick(i + 1, right);

}

}

int main()

{

quick(1, 8);

for (int i = 1; i <= 8; i++)

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

return 0;

}

Count Sort

정렬할 값의 범위가 좁을때 사용하면 효율적.

ex) 1,3,4,6,3,2,3,4,5,1,2,3,6 의 값을 소팅해야 한다면 1차원 배열에 해당 값의 인덱스의 값을 증가시키면 된다.

arr[1] = 2, arr[2] = 2, arr[3] = 4, arr[4] = 2, arr[5] = 1, arr[6] = 2 이므로,

arr[1]부터 저장된 값만큼 인덱스를 출력하면 1 1 2 2 3 3 3 3 4 4 5 6 6 으로 O(n)의 시간복잡도를 보인다.

하지만 값의 범위가 넓다면,

ex) 1, 100000 일 경우 값은 2개 뿐이지만 정렬을 하기 위해서는 크기가 100001인 배열이 필요하므로 메모리 공간의 낭비가 심하기 때문에 정렬할 값의 범위가 좁을때 사용하면 효율적이다.