본문 바로가기
반응형

알고리즘7

Sorting algorithm(정렬 알고리즘) - 4탄 Bubble sort(버블 정렬) 4. Bubble sort (거품 정렬, 버블 정렬) ▪ 바로 옆의 수와 비교해서 큰 수를 뒤로 정렬하는 방법 ▪ 시간 복잡도: O(n²) (예) # Bubble sort (거품정렬, 버블정렬) from typing import List def bubble(L: List) -> List: for i in range(len(L)): for j in range(len(L)-1): if L[j] > L[j+1]: L[j], L[j+1] = L[j+1], L[j] return L bubble([3, 91, 1, 5, 7, 2]) #답: [1, 2, 3, 5, 7, 91] 참고: https://ko.wikipedia.org/wiki/%EA%B1%B0%ED%92%88_%EC%A0%95%EB%A0%AC 2022. 7. 13.
Sorting algorithm(정렬 알고리즘) 3탄 - Merge Sort(합병 정렬) 3. Merge Sort (합병 정렬) ▪ 정렬된 두 리스트가 있을 때 (리스트1, 리스트2), 각각의 첫번째 수를 비교해서 작은 수를 정렬. → (리스트1의 첫번째 수가 정렬됐다고 가정하면,) 리스트1의 두번째 수와 남은 수 즉, 리스트2의 첫번째 수를 비교해서 정렬. → 동일한 방식으로 계속 진행해서 정렬된 하나의 리스트를 만듦. (그래서 병합이라고 하나 봄!!!ㅋㅋㅋ) ▪ 주의: 병합하기 전 두 리스트는 이미 정렬되어 있어야 함. 즉, Recursion을 이용해서 해당 두 리스트도 Merge sort 방식으로 정렬해야 함! ▪ 특징 : Memory Complexity는 Time Complexity는 (예) 정렬된 두 리스트 첫번째 수: 30 vs 2 → 2가 작으므로 2는 병합리스트 맨 앞에 위치... 2022. 7. 10.
Sorting algorithm(정렬 알고리즘) 2탄 - Insertion sort(삽입 정렬) 2. Insertion sort 삽입 정렬 - 왼쪽에서 2번째 수와 첫번째 수를 비교해서 작은 걸 첫번째에 위치시킴. (둘을 swap.) → 다음 수 즉, 왼쪽에서 3번째 수와 이미 정렬한 두 수를 비교하여 3번째 수의 위치를 찾아서 정렬시킴. → 같은 방식으로 4번째 수와 1~3번째 수를 비교해서 정렬시킴. → 계속 반복. 왼쪽에서 첫번째 수(70)는 이미 정렬된 것으로 간주. 왼쪽에서 두번째 수 30 < 70 → 30의 위치는 70의 앞이여야 하므로 30과 70 swap. 30, 70은 정렬됨. 100 vs 70 → 70 < 100 이므로 100은 70 다음이어야 함. 즉, swap할 필요 없음. 60 vs 100 → 60 < 100 이므로 100과 60 swap. 60 vs 70 → 60 < 70 .. 2022. 7. 1.
Sorting algorithm(정렬 알고리즘) 1탄 - Selection sort(선택 정렬) 💗 Sorting algorithm (정렬 알고리즘) : 데이터 등을 일정 순서대로 정렬, 나열하는 알고리즘. 💗 정렬 알고리즘 종류 1. Selection sort (선택 정렬) 2. Insertion sort (삽입 정렬) 3. Merge sort (합병 정렬) 4. Bubble sort (거품 정렬, 버블 정렬) 1. Selection sort (선택 정렬 알고리즘) - 가장 작은 수와 가장 왼쪽에 있는 수를 swap. → 가장 작은 수를 제외한 나머지 수들 중 최소 값과 가장 왼쪽에 있는 수를 swap. → 이런 식으로 계속 반복. 최소값: 5 가장 왼쪽 값: 70 5 ↔ 70 5는 정렬 완료. 정렬되지 않은 값들 중 최소값: 60 정렬되지 않은 값들 중 가장 왼쪽 값: 100 60 ↔ 100 동.. 2022. 6. 30.
반응형

티스토리툴바