hs-archive

퀵 정렬에 대해 알아보자. 얻어갈 지식 퀵 정렬 이해 퀵 정렬 병합 정렬과 마찬가지로 분할-정복 알고리즘이다. 대강의 순서는 아래와 같다. 값의 기준점이 될 기준 데이터(pivot)를 정한다. 기준 데이터(pivot)를 기준으로 작은 수는 왼쪽 큰 수는 오른쪽에 오도록 재배치한다. 그렇게 나뉜 두 개의 배열 속에서 또 기준점을 잡고 2번을 반복한다. 해당 과정을 더 이상 분할할 수 없을 때까지 반복한다. 조금 더 자세히 설명하면 피벗 값을 x, 왼쪽 끝 요소의 인덱스를 pl, 오른쪽 끝 요소의 인덱스를 pr이라고 할 때. pl은 인덱스 0부터 하나 씩 올라오며 x보다 큰 값을 찾고 반대로 pr은 오른쪽 끝 인덱스부터 x보다 작은 값을 찾는다. pl의 값이 pr보다 크지 않으면 서로의 값을 스왑하고 만약..

병합 정렬에 대해 알아보자 얻어갈 지식 병합 정렬 병합 정렬 퀵 정렬과 마찬가지로 분할-정복 알고리즘이다. 어레이 크기가 1이 될 때까지 반복적으로 분할하고 크기가 1이 되면 전체 어레이가 병합될 때 까지 병합한다. 스테이블한 정렬 알고리즘이며 버블 정렬, 선택 정렬, 삽입 정렬보다 빠르지만, O(N) 만큼의 추가 메모리 공간이 필요하다. 아래 사진과 영상을 보고 이해해보자. 병합 정렬 동영상 코드로 작성 def mergeSort(arr): if len(arr) > 1: mid = len(arr) // 2 L = arr[:mid] R = arr[mid:] mergeSort(L) mergeSort(R) i = j = k = 0 while i < len(L) and j < len(R): if L[i] < R..

삽입 정렬에 대해 알아보자. 얻어갈 지식 삽입 정렬 삽입 정렬 작은 데이터 셋에 효율적이다. 삽입 정렬은 간단한 정렬 알고리즘이다. 어레이는 정렬된 부분과 정렬되지 않은 부분으로 나뉜다. 정렬되지 않은 어레이의 값이 선택되고 정렬된 어레이의 올바른 위치에 배치된다. 삽입 정렬 예시 [ 12, 11, 13, 5, 6 ]이 있을 때 첫 번째 패스 0 번째 값과 1 번째 값 비교 12는 11보다 크므로 자리 바꿈 [ 11, 12, 13, 5, 6 ] 두 번째 패스 1 번째 값과 2 번째 값 비교 12는 13보다 작으므로 그대로 유지 [ 11, 12, 13, 5, 6 ] 세 번째 패스 2 번째 값과 3 번째 값 비교 13은 5보다 크므로 자리 스왑 12는 5보다 크므로 자리 스왑 11은 5보다 크므로 자리 스..

버블 정렬에 대해 알아보자. 얻어갈 지식 버블 정렬 버블 정렬 가장 간단한 정렬 알고리즘이다. 평균적으로 그리고 최악의 경우 시간 복잡성이 매우 높기 때문에 대규모 데이터 셋에는 적합하지 않다. 버블 정렬 예시 [ 5, 1, 4, 2, 8 ]로 되어있는 어레이가 있을 때 오름차순으로 정렬하면 아래와 같다. 첫 번째 패스 ( 가장 큰 수를 제일 마지막 자리로 옮기기 ) 5는 1보다 크므로 서로 자리를 바꾼다. [ 1, 5, 4, 2, 8 ] 5는 4보다 크므로 서로 자리를 바꾼다. [ 1, 4, 5, 2, 8 ] 5는 2보다 크므로 서로 자리를 바꾼다. [ 1, 4, 2, 5, 8 ] 5는 8보다 크지 않으므로 자리를 바꾸지 않는다. [ 1, 4, 2, 5, 8 ] 두 번째 패스 ( 두 번째로 큰 수를 뒤..