퀵

정렬 알고리즘 비교

bubble: 인접한 두개의 원소를 비교하여 자리를 교환하는 방식 첫번쨰 원소부터 인접한 원소끼리 계속 자리를 교환 한 단계가 끝나면 가장 큰 원소가 마지막 자리에 고정 정렬이 되어있어도 모든 수를 다 확인하기 때문에 가장 비효율적인 정렬 알고리즘 selection: 기준 위치에 맞는 원소를 선택하고 자리를 교환하는 방식 원소를 돌며 가장 작은 값을 찾는다. 첫번째 원소와 바꿔준다. 첫번째 원소를 제외하고 원소를 돌며 가장 작은 값을 찾는다. 두번째 원소와 바꿔준다. 계속 진행 버블 정렬을 일부 개선함 insertion: 정렬되어 있는 부분 집합에 정렬할 새로운 원소의 위치를 삽입하는 방식 정렬된 집합 S와 정렬되지 않은 집합 U로 나눈다. U에서 맨 앞의 원소를 꺼내서 S의 맨 뒤부터 비교해준다. 자신..

퀵 정렬(quick sort)

📔 퀵 정렬(quick sort) 이란 분할정복을 활용하여 구현하기 때문에 시간복잡도는 O(nlogn) 퀵이란 이름에 맞게 빠르다. 분할정복: 문제를 작은 2개의 문제로 분리하고 각각 해결한 후, 다시 모아 원래의 문제를 해결하는 방법. 보통 재귀함수 호출을 이용하여 구한다. 기준 값(pivot)을 기준으로 그 값보다 큰 값과 작은 값을 서로 교환한 뒤 기준 값을 기준으로 두개의 리스트로 나눈다. (기준 값의 왼쪽에는 작은 값, 오른쪽에는 큰 값) 대부분의 경우에는 퀵정렬이 가장 빠르다. (c언어의 정렬 알고리즘도 퀵정렬 기반) 비교 정렬 ( 다른 원소와의 비교 ) 📔 퀵 정렬(quick sort) 예제 맨앞의 값 3을 pivot 값으로 설정했다 ( 보통 가장 앞의 값을 pivot으로 설정) pivot값..