-
[Sorting #6] Quick Sort
Quick Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. quick sort 는 추가적인 메모리 사용 없이 Divide and Conquer 를 사용할 수 있습니다.pivot 을 이용해 divide 될 지점을 찾아주는 것이 핵심입니다. 그림으로 예를 들어 설명해보겠습니다. 이 리스트에서 첫번째 pivot 을 54 라고 합시다.( pivot 을 정하는 방법은 여러가지가 있지만, 예제에서는 첫번째 원소를 pivot 으로 하는 방법을 선택하고 있습니다.) 이제 이 pivot 을 기준으로 하고, 나머지 리스트 에 대해 leftmartk...
-
[Sorting #5] Merge Sort
Merge Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. sorting 알고리즘의 성능을 높이기 위해 Dived and Conquer 전략을 사용할 수 있습니다. Merge Sort 는 리스트를 재귀적으로 두개로 나누어 정렬 후 정렬된 부분들을 다시 합치는 방식입니다.base case는 merge 를 수행하는 부분이 되겠고, 그 조건은 리스트의 값이 하나 이하일 경우 입니다. 그림으로 예를 들어보겠습니다. 위의 그림은 Merge Sort 를 위해 리스트를 분할하는 과정을 나타냅니다.리스트의 원소가 하나 이하가 될 때 까지 계속...
-
[Sorting #4] Shell Sort
Shell Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. shell sort 는 조금 생소할 수도 있는 소팅 방법입니다.insertion sort 방식을 조금 개선한 방법인데, insertion sort 가 두 연속된 sublist 로 나누어 정렬하는 방식이었다면shell sort 는 일정 gap 을 가진 sublist 로 나누어 정렬하는 방식입니다. 그림을 보면서 설명하겠습니다. 이 그림은 gap 이 2 인 sublist 로 나누어 정렬한 예시입니다.그림처럼 일정한 gap 만큼 떨어진 값들을 하나의 sublist 로 묶어서 생각해 정렬하면...
-
[Sorting #3] Insertion Sort
Insertion Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. insertion sort 는 한 리스트 내에서 두 부분으로 리스트를 나누고, 뒤의 리스트의 값들을 하나씩 앞의 리스트에 정렬해서 넣는 방식입니다. 결론부터 말하자면 bubble sort 와 마찬가지로 성능이 좋지 않은 방법입니다. 그림으로 예를 들어보겠습니다. 편의상 앞의 list 를 sorted sublist , 뒤의 list 를 unsorted sublist 라고 이름붙여 보겠습니다. unsorted sublist 에 있는 값들을 차례로 sorted sublist 로 가져오는데, 이 때 가져오는...
-
[Sorting #2] Selection Sort
Selection Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. selection sort 는 리스트 중 가장 큰 값을 골라 뒤에서 부터 채우는 형식입니다.bubble sort 와는 달리 selection sort 는 리스트를 처음부터 끝까지 볼 때 한 번 의 swap 연산만 합니다. bubble sort 는 한 값을 정렬하기 위해 $n-1$ 번의 검사와 최대 $n-1$ 번의 swap 연산을 했다면,selection sort 는 $n-1$ 번의 검사와 한번의 swap 연산을 합니다. 그림으로 예시를 보겠습니다. 정렬되지 않은...
-
[Sorting #1] Bubble Sort
Bubble Sort Problem Solving with Algorithms and Data Structures using Python 을 공부하고 정리한 내용입니다. bubble sort 는 인접한 값을 비교하고 순서를 정렬하는 방법입니다.sorting 방법 중 가장 많이 알고있는 방법인데, 성능면에서는 우수하지 않습니다.compare 와 swapping 을 불필요하게 여러 번 하기 때문입니다. 그림으로 예를 들어보겠습니다. [54, 26, 93, 17, 77, 31, 44, 55, 20] 이라는 bubble sort 방식으로 정렬할 때, 처음 비교해야 하는 쌍은 총 8 ( 9-1 ) 개 입니다. 8쌍을 비교하고 나면, 리스트 내에서...