Study Blog

셰이커 정렬이란? 버블 정렬을 개선한 알고리즘으로, 양방향 버블 정렬, 칵테일 정렬, 칵테일 셰이커 정렬이라고도 부른다. 지난 글(https://vibeee.tistory.com/29)에서 버블 정렬로 3가지 코드를 살펴보았다.하지만 가장 큰 값이 맨 앞에 있는 경우 3가지 코드 모두 비효율적인 정렬 과정을 수행하는 것을 알 수 있었다. 다음 코드에서는 이 부분을 셰이커 정렬로 개선한 코드를 살펴본다.from typing import MutableSequencedef shaker_sort(a: MutableSequence) -> None: left = 0 right = len(a) - 1 last = right while left a[j]: # 앞의 값이 뒤보다 큰 경우에 교환 ..

버블 정렬이란?- 이웃한 두 원소의 대소 관계를 비교하고, 교환을 반복하는 알고리즘(=단순 교환 정렬)- 액체 속의 공기 방울이 가벼워서 위로 보글보글 올라오는 모습에 착안해서 붙인 이름 오름차순 정렬하는 버블 정렬의 첫 번째 패스 진행 과정은 다음과 같다.1) 오른쪽 끝에 있는 두 원소 9와 8에 주목한다.2) 9와 8의 위치를 교환한다.3) 다음 원소인 1과 8에 주목한다.4) 1과 8의 위치는 교환하지 않는다. 원소 수가 n인 배열에서 n - 1번 비교 & 교환을 하면 가장 작은 원소인 1이 맨 앞으로 이동한다. 이러한 과정을 패스라고 한다. 위와 같이 패스를 한 번 수행할 때마다 정렬할 대상은 1개씩 줄어든다. 그러므로 두 번째 패스의 비교 횟수는 첫 번째 패스보다 1번 적은 n - 2번이다. 패..

정렬이란? - 이름, 학번, 학점 등의 특정 키를 기준으로 대소 관계에 따라 데이터의 집합을 일정한 순서로 바꾸어서 늘어놓는 작업이다. - 값이 작은 데이터부터 앞쪽에 늘어놓는 것: 오름차순(ascending order) 예) a = [1, 2, 3, 4, 5] - 값이 큰 데이터부터 앞쪽에 늘어놓는 것: 내림차순(descending order) 예) a = [5, 4, 3, 2, 1] - 정렬 알고리즘은 시간 복잡도에 따라 성능이 좌우되고, 성능이 좋은 알고리즘일수록 구현 방법이 어려워진다. 정렬 알고리즘의 시간복잡도 - O(n²): 버블 정렬, 선택 정렬, 삽입 정렬, 셸 정렬(최악 O(n²), 최선O(n log n)) - O(n log n): 병합 정렬, 퀵 정렬, 힙 정렬 - O(n): 도수 정렬..