[알고리즘] 패스트캠퍼스 챌린지 21일차

퀵 정렬(Quick Sort)

• 정렬 알고리즘의 꽃
• 기준점(pivot 이라고 부름)을 정해서, 기준점보다 작은 데이터는 왼쪽(left), 큰 데이터는 오른쪽(right) 으로 모으는 함수를 작성함
• 각 왼쪽(left), 오른쪽(right)은 재귀용법을 사용해서 다시 동일 함수를 호출하여 위 작업을 반복함
• 함수는 왼쪽(left) + 기준점(pivot) + 오른쪽(right) 을 리턴함

 

기준점 pivot은 배열에서 첫번째 데이터로

pivot보다 작으면 왼쪽배열, 크면 오른쪽배열로 저장

왼쪽배열 + 기준점 + 오른쪽배열 모두 합쳐서 리턴해준다.

 

 

Swift 코드로 작성해봤다.

테스트도 성공!

func quickSort(array: [Int]) -> [Int] {
    if array.count <= 1 {
        return array
    }
    let pivot: Int = array[0]
    
    var left: [Int] = []
    var right: [Int] = []
    for index in 1..<array.count {
        if pivot > array[index] {
            left.append(array[index])
        } else {
            right.append(array[index])
        }
    }
    
    return quickSort(array: left) + [pivot] + quickSort(array: right)
    
}

 

방법 이해하고 그대로 코드로 옮겨주면 된다.

글로 설명되어있을 때에는 어려웠는데 엑셀로 차근차근 단계별로 설명해주시는 것 보고 금방 구현했다!

 

 

퀵 정렬 시간복잡도

병합정렬과 유사, 시간복잡도는 O(n log n)

• 단, 최악의 경우
  • 맨 처음 pivot이 가장 크거나, 가장 작으면
  • 모든 데이터를 비교하는 상황이 나옴
  • O(n²)

 

 

인증샷 퀵정렬 알고리즘 구현하기!!

 

오늘은 퀵정렬.

방법만 이해하면 쉽게 구현해볼 수 있었다.

강의자료에 리스트의 특정 데이터 기준으로 데이터 나누기 등등 퀵정렬 알고리즘 구현을 위한 기초적인 문제들이 단계별로 포함되어 있어서 먼저 생각하면서 그 문제들을 풀어내니, 퀵정렬 알고리즘을 좀더 빠르게, 쉽게 구현할 수 있었다.

 

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.