정렬(Sort)

정렬

정렬 알고리즘은 n개의 숫자가 입력으로 주어졌을 때, 사용자가 지정한 기준에 맞게 출력하는 알고리즘이다.

-N개의 숫자 오름차순 가정-

---

swap 함수 : 배열에서 특정 두 위치의 원소 바꾸기

void swap(int[] array, int i, int j){
	int num = array[i];
    array[i] = array[j];
    array[j] = num;
}

---

1.선택정렬

로직

배열의 앞에서부터 배열의 전체를 비교하여 가장 작은값을 찾은 후 가장 첫번째 배열의 값과 교체한다.
이후 다음 인덱스에도 동일한 과정을 반복하며 마지막 인덱스까지 반복한다.

복잡도

• 시간 : 처음부터 끝까지 n번 + n-1번..1까지 해야하므로 O(n^2)
• 공간 : 추가적인 메모리공간을 필요로 하지 않으므로 O(n)

구현

void SelectionSort(int[] array){
	int num = array.Length;
	for(int i =0 ; i < num-1 ; i++){
        int index = i;
    	for(int j = i+1; j < num ; j++){
        	if(array[index] > array[j]{
                index = j;
            }
            swap(array, i, j);
        }
    }
}

---

2.삽입정렬

로직

삽입정렬은 두번째 인덱스 부터 시작하여 앞의 인덱스의 요소들과 비교하여 해당 요소가 들어갈 위치에 넣는 방법.제한적인 경우 많이 사용
데이터셋이

복잡도

• 시간: 시작부터 끝까지 두번 돌아야하므로 O(n^2)
• 공간: 추가적인 메모리가 필요없으므로 O(n)

구현

void InsertionSort(int[] array){
	int length = array.Length;
    for(int i=1; i<length ; i++){
    	int key = i;
    	for(int j=i-1;j>=0;j--){
        	if(array[key]>array[j]){
            	return;
            }
            swap(array, i, j);
            key=j;
        }
    }
}

---

3.퀵정렬

로직

배열에서 피벗(Pivot)을 설정하고 피벗을 기준을 파티션을 나누어서 배열을 정렬함.
메모리가 제한적인 상황에서 데이터셋이 크지않을 때 유용함

복잡도

• 시간 복잡도 : O(nlogn) 최악의 경우 O(n^2)
• 공간 복잡도 : O(n)

구현

public static void QuickSortInternal(int[] array, int left, int right)
{
    if(left >= right) return;

    int pivot = Partition(array, left, right);

    QuickSortInternal(array, left, pivot - 1);
    QuickSortInternal(array, pivot + 1, right);
}

public static int Partition(int[] array, int left, int right)
{
    int i = left + 1, j = right;
    int pivotValue = array[left];

    while (i < j)
    {
        while(array[j] > pivotValue)
            j--;

        while(array[i] <= pivotValue && i < j)
            i++;

        Swap(array, i, j);
    }

    Swap(array, left, i);
    return i;
}

---

4.버블정렬

로직

첫번째 요소부터 인접한 요소를 배열끝까지 비교함 // 한스텝 마다 가장큰 요소가 배열이 됨.
추가적인 메모리 사용이 이루어지지 않음.

복잡도

• 시간복잡도 : O(n^2)
• 공간복잡도 : O(n)

구현

public static int[] BubbleSort(int[] array){
	int length = array.Length;
	for(int i = 0; i<n ; i++){
    	for(int j = 0 ; j < i ; j++){
        	if(int[j] > int[j+1]) Swap(array, j, j+1);
        }
    }
    return array;
}

---

5.합병정렬

로직

폰노이만 / 분할정복 / 안정정렬
배열들을 분할하여 정렬후에 합침

복잡도

• 시간 : O(nlogn)
• 공간 : O(n^2)

구현

int[] Merge(int[] array , int left, int mid, int right){
	//분할을 하기위한 원소의 개수 설정
	int n1 = mid -left +1;
    int n2 = right - mid;
    
    //위에서 설정한 원소의 개수로 배열 선언.
    int[] leftArray = new int[n1];
    int[] rightArray = new int[n2];
    
    //해당나뉜 어레이에 값 복사
    for(int i = 0 ; i < n1 ; i++){
    	leftArray[i] = arr[left + i];
    for(int j = 0 ; j < n2 ; j++){
    	rightArray[i] = arr[mid+1+j];
    }
    
    int leftIndex = 0, rightIndex = 0, mergedINdex = left;
    
    while(leftIndex < n1 && rightIndex < n2){
    	if(leftArray[leftIndex] <= rightArray[rightIndex]){
        	arr[mergedIndex] = leftArray[leftIndex];
            leftIndex++;
        }
        else{
        	arr[mergedIndex] = rightArray[rightIndex];
            rightIndex++;
            mergedIndex++;
        }
        mergedIndex++;
    }
    
    while(leftIndex < n1){
    	arr[mergedIndex] = leftArray[leftIndex];
        leftIndex++;
        mergedIndex++;
    }
    
    while(rightIndex < n2){
    	arr[mergedIndex] = rightArray[rightIndex];
        rightIndex++;
        mergedIndex++;
    }
}

public static void MergeSort(int[] arr, int left, int right){
	if(left < right){
    	int mid = left + (right - left) / 2;
        
        MergeSort(arr, left, mid);
        MergeSort(arr, mid+1, right);
        
        Merge(arr, left, mid, right);
    }
}

---

6. 힙정렬

로직

데이터들을 힙상태를 만족하는 이진트리형태에 집어넣은 다음 우선순위가 가장 높은 root의 값을 뽑아내어 정렬

복잡도

• 시간 : O(nlogn)
• 공간 : 정렬할때는 O(1) 추가적인 메모리소모 x

구현

---

cf) 분할 정복으로 분류

• 분할: 퀵 머지 힙
• 분할x : 버블 삽입 선택

cf) 안정/불안정 정렬로 분류

• 안정 : 버블 퀵 삽입
• 불안정 : 머지 힙 선택