[Udemy] JavaScript 알고리즘 & 자료구조 마스터클래스_Section 11

* 수업은 JS 기반이지만 Python으로 구현

Section 11

정렬 알고리즘

정렬 알고리즘이란 모음의 항목을 재배열하는 과정이다. 다음과 같은 이유로 알아두어야 한다.

1. 이미 존재하는 정렬 함수를 활용한다고 해도, 어떤 알고리즘이 사용되는지를 알아야 목적에 맞게 활용할 수 있다.
2. 상황에 따라 정렬하는 방식이 장점으로 작용할 때도 있고 단점으로 작용할 때도 있다.
3. 비판적 사고를 요하는 면접 질문에 자주 활용된다.

기본 내장 자바스크립트 정렬

Array.sort()는 유니코드 코드 포인트를 따르는데, 배열의 모든 항목이 문자열로 변환되고 그 다음에 해당 유니코드 값을 선택한 후 항목이 정렬된다. JS에서 내장 정렬 메소드는 선택적 비교 함수를 인자로 전달받는다. 이를 이용하면 정렬 방식을 정할 수 있다.

# JS

// 1번
[6, 4, 14, 11].sort(}


// 2번
fuction Compare(num1, num2){
	return num1 - num2;
    }
    
[6, 4, 14, 11].sort(Compare);

/*
숫자 배열을 정렬한 결과를 기대할 때 1번을 수행하고 2번의 결과를 생각하지만
실제로는 1번을 수행할 경우 정렬이 원하는대로 되지 않는 경우가 있다고 한다.
JS는 정말 특이하군
*/

버블 정렬: 개요

자주 사용되지 않지만, 구현 방식이 특이하고 다른 알고리즘이 왜 효율적인지 이해하는데 도움이 된다.

두 요소를 비교하여 앞의 요소가 더 큰 경우 뒷 요소와 교환을 합니다. 이후 다음 두 요소를 비교하여 아까와 마찬가지로 더 큰 요소가 뒤로 간다. 한 바퀴를 돌 때마다 비교한 요소 중 가장 큰 요소가 제일 끝으로 가게 되어, 비교를 반복할 수록 정렬해야 할 항목의 수가 감소하게 된다.

• Swap 적용하는 방법: JS 버전에 따라 두 가지 방법이 있다. 관련 사항은 이 블로그를 참조
  • ES5 ver
    • 함수에 tmp를 사용해 하나의 값을 옮기고 나머지에 tmp값을 적용하는 방법
  • ES2015 ver
    • 전자, 후자 = 후자, 전자 의 형태로 작성하는 것

버블 정렬: 구현

• i 변수를 이용하여 배열의 끝에서 루프를 시작해 맨 앞에서 끝나는 루프
• 내부 루프는 j 변수를 이용해 배열의 시작에서 i - 1번째까지 도는 루프
• 만약 배열의 j번째가 배열의 j+1번째의 값보다 크다면 두 값을 교환
• 정렬된 배열을 return

# BubbleSort  ES5ver
def Bubble(arr):
    # i의 값은 j 루프에서 활용되는데, 배열 요소의 비교를 어디까지 수행할지를 결정
    # 만약 첫 i가 배열의 길이까지인 경우
    # j의 비교는 (배열의 길이 - 1) 번째 와 (배열의 길이) 번째가 될 것이다.
    for i in range(len(arr), 0, -1):
        for j in range(i - 1):
            # 비교하는 과정을 확인하기 위한 것
            print(i, j, arr[j], arr[j+1])
            # 만약 앞 요소가 뒷 요소보다 크다면 자리를 바꿔라
            if arr[j] > arr[j+1]:
                # swap
                tmp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = tmp
    # 정렬된 배열을 return
    return arr
    
Bubble([33, 14, 223, 54, 21, 9])
Bubble([33, 14, 223, 21, 9, 0, 14])

# BubbleSort ES2015 ver
def Bubble(arr):
    # i의 값은 j 루프에서 활용되는데, 배열 요소의 비교를 어디까지 수행할지를 결정
    # 만약 첫 i가 배열의 길이까지인 경우
    # j의 비교는 (배열의 길이 - 1) 번째 와 (배열의 길이) 번째가 될 것이다.
    for i in range(len(arr), 0, -1):
        for j in range(i - 1):
            # 비교하는 과정을 확인하기 위한 것
            print(i, j, arr[j], arr[j+1])
            # 만약 앞 요소가 뒷 요소보다 크다면 자리를 바꿔라
            if arr[j] > arr[j+1]:
                # swap
                arr[j], arr[j+1] = arr[j+1], arr[j]
    # 정렬된 배열을 return
    return arr
    
Bubble([33, 14, 223, 54, 21, 9])
Bubble([33, 14, 223, 21, 9, 0, 14])

버블 정렬: 최적화

배열의 거의 정렬된 상태에서는 버블 정렬이 이미 정렬된 배열의 정렬을 위한 비교 수행하지 않도록 해야 한다. 만약 마지막 비교와 정렬 과정에서 한 번도 교환이 없었다면, 정렬이 완료된 것과 같다.

# BubbleSort optimized ver
def Bubble(arr):
    # i의 값은 j 루프에서 활용되는데, 배열 요소의 비교를 어디까지 수행할지를 결정
    # 만약 첫 i가 배열의 길이까지인 경우
    # j의 비교는 (배열의 길이 - 1) 번째 와 (배열의 길이) 번째가 될 것이다.
    for i in range(len(arr), 0, -1):

        # 교환이 이루어졌는가를 확인한 bool 변수, 초기값은 True
        NoSwaps = True

        for j in range(i - 1):
            # 비교하는 과정을 확인하기 위한 것
            print(i, j, arr[j], arr[j+1], NoSwaps)
            # 만약 앞 요소가 뒷 요소보다 크다면 자리를 바꿔라
            if arr[j] > arr[j+1]:
                # swap
                tmp = arr[j]
                arr[j] = arr[j+1]
                arr[j+1] = tmp
                # 교환이 이루어졌다면, False
                NoSwaps = False
        # 만약 배열 한 바퀴를 도는 동안 교환이 한 번도 이루어지지 않았다면
        # NoSwaps가 True이므로, for 문을 종료한다
        if NoSwaps:
                break
    # 정렬된 배열을 return
    return arr
    
Bubble([9, 1, 2, 3, 5, 6, 8])

버블 정렬: 빅오 복잡도

• 시간복잡도
  • Best: O(n)
  • Average: O(n^2)
  • Worst: O(n^2)
• 공간복잡도
  • O(1)