[알고리즘]정렬의 기본.

정렬(sort)

주어진 데이터를 정해진 기준에 따라 순서를 재배열 하는 작업.

오름차순 or 내림차순

 

정렬 알고리즘의 종류

버블정렬(bubble sort)

선택정렬(selection sort)

삽입정렬(insertion sort)

위의 세가지 정렬들은 구현은 단순하나 비효율적이다.

 

아래의 정렬들은 구현은 복잡하나 다소 효율적이다.

쉘정렬(shell sort)

병합정렬(merge sort)

퀵정렬(quick sort)

힙정렬(heap sort)

기수정렬(radix sort)

 

 

버블 정렬

:정렬되지 않은 부분에서 인접한 두 원소의 크기를 비교하여 교환하는 작업을 반복.

시간복잡도 = O(n^2)

void bubble_sort(int data[],int n)
{
	for(int i=0;i<n-1;i++){
    	for(int j=n-1;j>i;j--){
        if(data[j]<data[j-1]) //오름차순
        	swap(data[j],data[j-1]);
        }   
    }
}

 

선택 정렬

:정렬되지 않은 원소들 중에서 최소값 원소를 찾아 맨 왼쪽 원소와 교환.

시간복잡도 = O(n^2)

void selection_sort(int data[],int n)
{
	for(int i=0;i<n-1;i++){
    	int idx=i;
        for(int j=i+1;j<n;j++){
        if(data[j]<data[idx]){
        	idx=j;
        }
        swap(data[i],data[idx]);
      }  
    }
}

 

삽입 정렬

:정렬되지 않은 부분의 첫 번째 원소를 정렬된 부분의 알맞은 위치에 삽입하는 과정을 반복.

시간복잡도 = O(n)~O(n^2)

void insertion_sort(int data[], int n)
{
	for (int i = 1; i < n; i++) {
		int key = data[i];
		int j = i - 1;
		while (j >= 0 && data[j] > key) {
			data[j + 1] = data[j];
			j--;
		}
		data[j + 1] = key;
	}
}