선택 정렬(Selection Sort)

최선 : $n^2$ 평균 : $n^2$ 최악 : $n^2$

1번부터 n까지 훑어서 나온 가장 작은 수 : 1번째
2번부터 n까지 훑어서 나온 가장 작은 수 : 2번째

위 과정을 (n-1)번 반복한다.

속도는 항상 $\dfrac{n(n-1)}{2}$ 이다.

public void selectionSortRecursive(int[] data){
    selectionSortRecursive(data, 0);
}

private void selectionSortRecursive(int[] data, int start){
    if(start < data.Length - 1){
        swap(data, start, findMinimumIndex(data, start));
        selectionSortRecursive(data, start + 1);
    }
}

private int findMinimumIndex(int[] data, int start){
    int minPos = start;

    for(int i = start + 1; i < data.Length; i++){
        if(data[i] < data[minPos])
            minPos = i;
    }

    return minPos;
}

private void swap(int[] data, int index1, int index2){
    if(index1 != index2){
        int tmp = data[index1];
        data[index1] = data[index2];
        data[index2] = tmp;
    }
}

정렬 이미지 접기/펼치기

정순

역순

랜덤

삽입 정렬(Insertion Sort)

최선 : $n$ 평균 : $n^2$ 최악 : $n^2$

k번째 원소를 1부터 k-1까지 비교 후 적절한 위치에 끼워넣고 그 뒤의 자료를 한 칸씩 뒤로 밀어낸다.

public void InsertionSort(int[] data){
    for (int which = 1; which < data.Length; which++){
        int val = data[which];

        for (int i = which - 1; i >= 0; i--){
            if (val < data[i]){
                data[i + 1] = data[i];
                if (i == 0)
                    data[i] = val;
            }
            else{
                data[i+1] = val;
                break;
            }
        }
    }
}

정렬 이미지 접기/펼치기

정순

역순

랜덤

</div>

버블 정렬(Bubble Sort)

최선 : $n$ 평균 : $n^2$ 최악 : $n^2$

1번과 2번을 비교하여 정렬하고, 2번과 3번 … n-1번 n번의 비교하여 정렬한다.
다시 처음으로 돌아가 n-2번 n-1번 까지 비교한다.

위 과정을 (n-1)번 반복한다.

static void BubbleSort(int[] data)
{
    for (int i = 0; i < data.Length; i++) {
        int swap = 0;
        for (int j = 1; j < data.Length - i; j++)
        {
            if (data[j-1] > data[j])
            {
                swap++;
                Swap(data, j);
            }
        }
        if (swap == 0) break;
    }
}
static void Swap(int[] data, int index)
{
    int temp = data[index];
    data[index] = data[index - 1];
    data[index - 1] = temp;
}

정렬 이미지 접기/펼치기

정순

역순

랜덤

퀵 정렬(Quick Sort)

최선 : $n\log(n) $ 평균 : $n\log(n)$ 최악 : $n^2$

static void QuickSort(int[] data, int left, int right)
{
    int pivotValue = data[(left + right) / 2];
    int i = left;
    int j = right;

    while (i <= j)
    {
        while (data[i] < pivotValue) i++;
        while (data[j] > pivotValue) j--;
        if (i <= j)
        {
            Swap(data, i, j);
            i++;
            j--;
        }
    }
    if (left < j)
    {
        QuickSort(data, left, j);
    }
    if (right > i)
    {
        QuickSort(data, i, right);
    }
}
static void Swap(int[] data, int index1, int index2)
{
    int temp = data[index1];
    data[index1] = data[index2];
    data[index2] = temp;
}