'정렬 알고리즘' 태그의 글 목록

정렬 알고리즘

앞서 다룬 네 가지 정렬 알고리즘을 비교하면 다음과 같습니다 추가적으로 대부분의 프로그래밍 언어에서 지원하는 표준 정렬 라이브러리는 최악의 경우에도 O(NlogN) 을 보장하도록 설계되어 있다 정렬알고리즘 평균시간 복잡도 공간 복잡도 특징 선택정렬 O(N²) O(N) 아이디어가 매우 간단하다 삽입정렬 O(N²) O(N) 데이터가 거의 정렬되어 있을 때는 가장 빠르다 퀵정렬 O(NlogN) O(N) 대부분의 경우에 가장 적합하며, 충분히 빠르다 계수정렬 O(N + K) O(N + K) 데이터의 크기가 한정되어 있는 경우에만 사용이 가능하지만 매우 빠르게 동작한다 선택 정렬과 기본 정렬 라이브러리 수행 시간 비교 from random import randint import time # 배열에 10,000개의..

Python/이코테 2022. 6. 19. 18:29

[Python] 정렬 알고리즘(3)-삽입 정렬

처리되지 않은 데이터를 하나씩 골라 적절한 위치에 삽입합니다. 선택정렬에 비해 구현 난이도가 높은 편이지만 실행시간 측면에서 더 효율적으로 동작합니다. 삽입 정렬 소스코드 (Python) arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(1, len(arr)): for j in range(i, 0, -1): #(start, end, step) if arr[j] < arr[j -1]: # 한 칸씩 왼쪽으로 이동 arr[j], arr[j -1] = arr[j -1], arr[j] else: # 자기보다 작은 데이터를 만나면 그 위치에서 멈춤 break 삽입 정렬의 시간 복잡도 삽입 정렬의 시간 복잡도는 O(N²)이며, 선택 정렬과 마찬가지로 반복문이 두 번 중첩되어..

Python/이코테 2022. 6. 19. 04:02

[Python] 정렬 알고리즘(2)-선택정렬

처리되지 않은 데이터 중에서 가장 작은 데이터를 선택해 맨 앞에 있는 데이터와 바꾸는 것을 반복합니다. 선택 정렬 동작 예시 선택 정렬 소스코드(Python) arr = [7, 5, 9, 0, 3, 1, 6, 2, 4, 8] for i in range(len(arr)): min_index = i # 가장 작은 원소의 인덱스 for j in range(i + 1, len(arr)): if arr[min_index] > arr[j]: min_index = j arr[i], arr[min_index] = arr[min_index], arr[i] # 스와프 print(arr) 선택 정렬의 시간 복잡도 선택 정렬은 n번 만큼 가장 작은 수를 찾아서 맨 앞으로 보내야 합니다. 구현방식에 따라서 사소한 오차는 있을 ..

Python/이코테 2022. 6. 19. 03:22