[CS스터디 #01] 정렬 알고리즘

 

 

 

💻 알고리즘: Algorithm

 

선택 정렬 (Selection Sort)

 

   "가장 작은 데이터를 선택하여 맨 앞의 데이터와 순서를 바꾼다"

   i번째 위치의 값에 대하여 i+1번째부터 마지막 원소까지 비교하여 가장 작은 값을 찾아내 현재 i번째 위치의 값과 자리를 바꿔주는 연산을 수행한다. 즉 0~i-1까지 이미 오름차순으로 찾아낸 정리된 값들은 두고, 현재 위치에 들어갈 최소값을 정렬이 안된 원소들 사이에서 찾아내 선택하는 알고리즘이다. 최소값을 찾는 전체 탐색을 모든 원소에 대해 수행하므로 Time Complexity는 O(N^2)이 된다.

 

 >> 특징

• 가장 원시적인 정렬 알고리즘이다.
• 시간복잡도: O(N^2)

 >> 소스코드

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

#파이썬
arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]
n = len(arr)

for i in range(0, n-1):
    least = i
    for j in range (i+1, n):
        if arr[least] > arr[j]:
            least = j
    arr[i], arr[least] = arr[least], arr[i]

 

 

 

 

버블 정렬 (Bubble Sort)

 

 인접한 두 개의 데이터를 비교해가며 정렬을 진행하는 방식이다.

   한 번의 연산마다 정렬이 안된 모든 값들에 대해 인접 비교를 수행하며, 그 중에서 가장 큰 값이 배열의 맨 끝으로 정렬된다. 이와 같은 연산을 n번 반복하므로 Time Complexity는 O(N^2)이 된다.

 

 >> 특징

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

 >> 소스코드

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

#파이썬
arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]
n = len(arr)

for i in range(n-1):
    for j in range (n-1-i):
        if arr[j] > arr[j+1]:
            arr[j], arr[j+1] = arr[j+1], arr[j]

 

 

 

 

삽입 정렬 (Insertion Sort)

 

 "데이터를 하나씩 확인하며, 적절한 위치에 삽입한다."

 n개의 원소를 가진 배열을 정리할 때, i번째를 정렬할 순서라고 한다면 0부터 i-1번째까지는 정렬되어 있다는 가정 하에 i번째 원소가 들어갈 위치를 찾는 연산을 수행한다. 이 과정을 배열의 마지막 원소까지 반복해주므로 Time Complexity는 O(N^2)이 된다.

 

 >> 특징

•  필요할 때만 위치를 바꾸므로 데이터가 거의 정렬되어 있을 때 효과적이다.
•  시간복잡도: O(n^2)
•  단, 거의 정렬되어 있는 상태라면 루프 안의 반복문이 1회만 실시되고 말기 때문에 매우 빠르게 동작하여 O(N)의 성능을 보인다. 

 >> 소스코드

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

#파이썬
arr = [1, 5, 3, 4, 2, 88, 4, 7, -1, 0]
n = len(arr)

for i in range(1, n):
    key = arr[i]
    j = i-1
    while j >= 0 and arr[j] > key:
        arr[j+1] = arr[j]
        j = j-1
    arr[j+1] = key

 

 

 

 

퀵 정렬 (Quick Sort)

 

   "기준이 되는 피벗(Pivot)을 정한 뒤 큰수와 작은 수를 교환한 후 리스트를 반으로 나누는 방식으로 동작한다."

   피벗을 어떻게 정하는 지를 미리 명시해야 하는데, 보통 '리스트에서 첫 번째 데이터를 피벗으로 정한다'는 호어 분할 방식을 기준으로 삼는다.

   피벗을 설정한 뒤에는 왼쪽부터 피벗보다 큰 데이터를 찾고, 오른쪽부터 피벗보다 큰 데이터를 찾으며 서로 교환한다. 

 

 >> 특징

• 파이썬이나 자바에서 정렬 내장함수의 기본이 된다.
• 재귀함수와 동작 원리가 같다.
• 시간복잡도: 평균적으로 O(N^2), 최악의 경우 O(N^2)이다. 피봇값의 선택에 따라 크게 달라진다. 
• 일반적으로 원소의 개수가 적어질수록 나쁜 중간값이 선택될 확률이 높아지기 때문에, 원소의 개수에 따라 퀵 정렬에 다른 정렬을 혼합해서 쓰는 경우가 많다.
• 병합 정렬은 항상 정중앙을 기준으로 단순 분할 후 병합 시점에서의 값의 비교 연산이 발생하는 반면에, 퀵 정렬은 분할 시점부터 비교연산이 일어나기 때문에 그 이후 병합에 들어가는 비용이 매우 적거나 구현 방법에 따라 아예 병합을 하지 않을 수도 있다.

>> 소스 코드

//자바
public class QuickSorter {
    public static List<Integer> quickSort(List<Integer> list) {
        if (list.size() <= 1) return list;
        int pivot = list.get(list.size() / 2);

        List<Integer> lesserArr = new LinkedList<>();
        List<Integer> equalArr = new LinkedList<>();
        List<Integer> greaterArr = new LinkedList<>();

        for (int num : list) {
            if (num < pivot) lesserArr.add(num);
            else if (num > pivot) greaterArr.add(num);
            else equalArr.add(num);
        }

        return Stream.of(quickSort(lesserArr), equalArr, quickSort(greaterArr))
                .flatMap(Collection::stream)
                .collect(Collectors.toList());
    }
}

#파이썬
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    lesser_arr, equal_arr, greater_arr = [], [], []
    for num in arr:
        if num < pivot:
            lesser_arr.append(num)
        elif num > pivot:
            greater_arr.append(num)
        else:
            equal_arr.append(num)
    return quick_sort(lesser_arr) + equal_arr + quick_sort(greater_arr)

 

 

 

 

 

병합 정렬 (Merge Sort)

 

 Divide and Conquer. 즉, 어떤 문제를 우선 작게 쪼개고 난 후, 다시 조합하여 원래의 문제를 푸는 방식의 알고리즘이다.

 주어진 배열을 최소길이가 될 때까지 계속해서 절반으로 분할하여 부분 리스트로 나누고, 인접한 부분 배열끼리 정렬하여 합치는 과정을 반복한다.

 

 >> 특징

• 시간복잡도: O(N*logN)
• 절반씩 분할하는 과정에서 O(logN)의 시간이, 병합하며 모든 값들의 순서를 비교하는 O(N)의 시간이 소모된다. 
• 두 개의 배열을 병합할 때, 병합 결과를 담아 놓을 배열이 추가로 필요하기 때문에 공간 복잡도는 O(N)이 된다.
• 다른 정렬 알고리즘과 달리, 인접한 값들 간에 상호 자리 교대(swap)가 일어나지 않는다.

 >> 소스코드

// 자바
public class MergeSorter {
    public static int[] sort(int[] arr) {
        if (arr.length < 2) return arr;

        int mid = arr.length / 2;
        int[] low_arr = sort(Arrays.copyOfRange(arr, 0, mid));
        int[] high_arr = sort(Arrays.copyOfRange(arr, mid, arr.length));

        int[] mergedArr = new int[arr.length];
        int m = 0, l = 0, h = 0;
        while (l < low_arr.length && h < high_arr.length) {
            if (low_arr[l] < high_arr[h])
                mergedArr[m++] = low_arr[l++];
            else
                mergedArr[m++] = high_arr[h++];
        }
        while (l < low_arr.length) {
            mergedArr[m++] = low_arr[l++];
        }
        while (h < high_arr.length) {
            mergedArr[m++] = high_arr[h++];
        }
        return mergedArr;
    }
}

# 파이썬
def merge_sort(arr):
    if len(arr) < 2:
        return arr

    mid = len(arr) // 2
    low_arr = merge_sort(arr[:mid])
    high_arr = merge_sort(arr[mid:])

    merged_arr = []
    l = h = 0
    while l < len(low_arr) and h < len(high_arr):
        if low_arr[l] < high_arr[h]:
            merged_arr.append(low_arr[l])
            l += 1
        else:
            merged_arr.append(high_arr[h])
            h += 1
    merged_arr += low_arr[l:]
    merged_arr += high_arr[h:]
    return merged_arr

 

 최적화 코드도 있지만, 이 글에서는 이 정도로만 정리하겠다.

 

 

 

 

힙 정렬 (Heap Sort), 계수 정렬 (Count Sort), 기수 정렬 (Radix Sort)

 정리 중...

 

 

 

 

 

 

 

❓❓❓

• 54321로 정렬된 배열이 있을 때, 이를 오름차순으로 정리하려면 어떤 정렬을 사용하는 것이 좋은가?
• 원소들이 랜덤으로 배치된 배열이 있을 때, 어떤 정렬을 사용하는 것이 좋은가?
• 자릿수가 모두 같은 수가 담긴 배열이 있을 때, 어떤 정렬을 사용하는 것이 좋은가? 

 

 

 

 

 

 

 

 

 

💎 💎 💎

 

 

Ｐｏｓｔｅｄ Ｂｙ ＳＡＹ

𝘛𝘩𝘢𝘯𝘬𝘴 𝘧𝘰𝘳 𝘳𝘦𝘢𝘥𝘪𝘯𝘨