1. 간단한 정렬 알고리즘

정렬 : 자료들을 크기 순서대로 나열하는 것

1. 선택 정렬
2. 버블 정렬
3. 삽입 정렬

2. 선택 정렬

각 루프마다 최대 원소를 찾아 마지막 원소와 교환하고 다음 루프에 마지막 원소를 제외. 하나의 원소만 남을 때까지 루프 반복

Algorithm selectionSort(a, n)
    for i = n-1 to 1 by -1
        // a[0]부터 a[i]까지 중 가장 큰 원소 찾기
        index = 0
        for j = 1 to i                
            if (a[index] < a[j]) then
                index = j
                
        // a[index]와 a[i] 교환
        temp = a[index]
        a[index] = a[i]
        a[i] = temp

시간복잡도 :
W(n) = B(n) = A(n) : O(n^2)

3. 버블 정렬

각 루프마다 처음부터 마지막까지 차례대로 인접한 두 원소 비교 후 정렬. 해당 루프에서 최대값이 마지막으로 이동하므로 다음 루프에 마지막 원소를 제외.

Algorithm bubbleSort(a, n)
    for i = n-1 to 1 by -1
        for j = 0 to i-1
            if (a[j] > a[j+1]) then
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp

시간복잡도 :
W(n) = B(n) = A(n) : O(n^2)

3-1. 개선된 버블 정렬

버블 정렬 과정 중 교환이 일어나지 않으면 정렬되어 있음을 의미. 따라서 알고리즘 종료

Algorithm improved_bubbleSort(a, n)
    for i = n-1 to 1 by -1
        sorted = True           // 정렬 상태 플래그
        for j=0 to i-1
            if (a[j] > a[j+1])
                 temp = a[j]
                 a[j] = a[j+1]
                 a[j+1] = temp
                 sorted = False // 교환 발생 시 정렬 안돼있음
        if (sorted)
            break

시간복잡도 :
W(n) : O(n^2)
B(n) : O(n)

4. 삽입 정렬

a[0]부터 a[i-1]까지 정렬되어 있을 때 a[i]를 포함하여 정렬하는 알고리즘

Algorithm insertionSort(a, n)
    for i = 1 to n-1            // 정렬 안된 원소들
        temp = a[i]             // 삽입할 원소
        j = i-1
        while j >= 0 and a[j] > temp:           // 정렬된 원소들  
            a[j+1] = a[j]
            j -= 1
        a[j+1] = temp

시간 복잡도 :
W(n) = A(n): O(n^2)
B(n) : O(n)

5. 간단한 정렬 알고리즘 정리