[개념] 정렬 알고리즘

선택 정렬(Selection Sort)

첫 번째 자리에 가장 작은 요소를 넣고, 두 번째 자리에 그 다음 가장 작은 요소를 넣고....

가장 작은 요소를 찾으면 첫 번째 자리에 있는 요소와 교환

 

void selectionsort(int arr[], int size){
	int minIndex;
    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;
        }
        swap(&arr[i], &arr[minIndex]);
    }
}

 

 

삽입 정렬(Insertion Sort)

key 원소 값의 알맞은 자리를 찾아 삽입

key보다 큰 값들은 하나씩 밀어버리고 작은 값을 만났을 때 그 뒷자리에 삽입

 

void insertionSort(int arr[], int size){
	for(int 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;
    }
}

 

버블 정렬(Bubble Sort)

현재 배열 요소와 그 다음 배열 요소를 비교하여 조건에 맞으면 교환 

 

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

 

 

합병 정렬(Merge Sort)

두 개의 배열로 계속 쪼게 나간 뒤, 합치면서 정렬해 최후에는 하나의 정렬을 출력한다. 

 

퀵 정렬(Quick Sort)

pivot point의 값을 정한 후 left와 right을 비교하면서 pivot point보다 작으면 left를 하나 증가시키고 비료한다.

 

//수정이 필요할듯
void quickSort(int left, int right, int arr[]){
	int pivot = arr[left];
    int less = left;
    int more = right + 1;
    
    if(left < right){
    	while(less < more){
        	while(less <=  right && arr[less] < pivot)
            	less++;      
            while(more <= left && arr[more] > pivot);
           	   	more--;
            if(less < more) swap(&arr[less], &arr[more]);
    	}
        swap(&arr[left], &arr[more]);
        quickSort(left, more - 1, arr);
        quickSort(more + 1, right, arr);
    }
}