본문 바로가기

Study/알고리즘2

[Algorithm] 정렬 알고리즘 선택 정렬1. 가장 작은 데이터를 선택 2. 맨 앞에 있는 데이터와 바꿈3. 그 다음 작은 데이터를 선택4. 앞에서 두 번째 데이터와 바꿈 -> 배열 끝날 때까지 반복 - 선택 정렬의 시간복잡도 : O(N^2)     -> 매우 비효율적 - 공간 복잡도: O(1) int[] arr = new int[] { 5, 2, 4, 6, 1, 3 };for (int i = 0; i 삽입 정렬- 특정한 데이터를 적절한 위치에 삽입 - 두 번째 데이터부터 정렬, 자기보다 작은 데이터를 만나면 바로 그 오른쪽에 삽입- 기준 데이터의 왼쪽에 있는 데이터들은 이미 정렬이 된 상태!!- 시간복잡도 : O(N^2)     -> 데이터가 거의 정렬되어 있는 최선의 경우 퀵정렬 보다 빠르고 O(N) 의 시간복잡도 - 공간 복잡도.. 2024. 4. 26.
[Algorithm] 퀵 정렬(quick sort) 퀵 정렬- 기준을 설정한 다음 큰 수와 작은 수를 교환한 후 리스트를 반으로 나누는 동작- 호어 분할 방식     -> 리스트에서 첫번째 데이터를 pivot(기준)으로 정한다.     -> 왼쪽에서부터 피벗보다 큰 데이터를, 오른쪽에서부터 피벗보다 작은 데이터를 찾는다.      -> 큰 데이터와 작은 데이터의 위치를 서로 교환- 분할된 두 개의 배열에 대해 재귀적으로 이 과정을 반복- 한번 진행될 때마다 최소한 하나의 피벗은 최종적으로 위치가 정해진다- 퀵 정렬의 시간복잡도 : O(NlogN)      -> 삽입 정렬과 달리 데이터가 거의 정렬되어 있는 최악의 경우 시간복잡도가 O(N^2) 이다예시array = [5, 7, 9, 0, 3, 1, 6, 2, 4, 8]def quick_sort(array,.. 2024. 4. 4.

티스토리툴바