정렬 알고리즘
-
[JAVA/자료구조] 퀵 정렬(Quick Sort)Language/Java 2021. 6. 13. 17:27
평균 수행 시간이 O(logN)인 알고리즘 퀵 정렬(Quick Sort), 병합 정렬(Merge Sort), 힙 정렬(Heap Sort) 한번 수행될때 마다 정렬되어야 하는 수의 범위가 1/2로 줄어드는 경우 사용한다. 퀵 정렬 이외의 다른 알고리즘은 추가적인 메모리가 필요하다. 퀵 정렬(Quick Sort) 퀵 정렬은 n개의 데이터를 정렬할 때 최악의 경우 O(n^2)번의 비교를 수행하고, 평균적으로 O(logN)번의 비교를 수행한다. 퀵 정렬은 찰스 앤터니 리처드호어가 개발한 정렬 알고리즘이다. 원소들 중에 같은 값이 있는 경우 같은 값들의 정렬 이후 순서가 초기 순서와 달라질 수 있기 때문에 불안정 정렬에 속한다. 퀵 정렬(Quick Sort) 구현 퀵 정렬은 분할 정복 방법을 통해 리스트를 정렬한..
-
[JAVA/자료구조] 선택 정렬(Selection Sort)Language/Java 2021. 6. 12. 23:11
평군 수행 시간 O(n^2) 알고리즘 버블 정렬(Bubble Sort) 삽입 정렬(Insertion Sort) 선택 정렬(Selection Sort) 각 요소가 다른 요소와 평균 한번 이상 씩 비교를 하여 정렬된다. 선택 정렬(Selection Sort) 제자리 정렬 알고리즘 중 하나이다. 1. 주어진 리스트 중 최솟값을 찾는다. 2. 그 값을 맨 앞에 위치한 값과 교체한다. 3. 맨 처음 위치를 뺀 나머지 리스트를 같은 방법으로 교체한다. 시간 복잡도는 O(n^2)으로 느리지만, 메모리가 제한적인 경우 성능상의 이점이 존재한다. 선택 정렬(Selection Sort) 구현 선택 정렬(Selection Sort) 구현 결과 반복 - 1 10 50 70 80 60 20 40 30 반복 - 2 10 20 7..