유제필의 개발 블로그

요약 시간 복잡도 : O(n log n) ~ O(n ^ 2) 정렬할 데이터에서 피벗을 기준으로 두 개의 비균등한 크기로 분할하는 작업을 반복 피벗 이하의 그룹과 이상의 그룹이 왼쪽, 오른쪽으로 분리되었을 경우 배열을 다시 분할 요소가 1개가 되었을 때 분할을 멈춤 퀵 정렬(Quick Sort) 퀵 정렬이란 정렬할 데이터에서 피벗(pivot)을 기준으로 두 개의 비균등한 크기로 분할하고 분할된 부분 리스트를 정렬하는 알고리증믈 말한다. 퀵 정렬은 가장 빠른 정렬 알고리즘으로, 찰스 앤터니 리처드 호어(C. A. R. Hoare)가 붙인 이름으로, 속도가 빠른 만큼 많이 사용되는 정렬 알고리즘이다. 만약 어떤 학생 그룹이 있고, 수가 8명이며 키 순서대로 정렬해야 되는 구조가 있다. 먼저 임의의 학생 A를 ..

선택 정렬(Selection Sort) 요약 시간 복잡도 : O(n ^ 2) 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 정렬 알고리즘 배열의 가장 작은 값을 찾아 맨 처음 요소와 위치를 변경하는 작업을 반복하여 정렬을 수행 같은 값이 있을 경우 상대적인 위치가 변경될 수 있어 안전하지 않음 배열의 크기를 알고 있기 때문에 이동 횟수를 미리 알 수 있다는 장점이 있음 단순 선택 정렬이란 단순 선택 정렬이란 가장 작은 요소부터 선택해 알맞은 위치로 옮겨서 순서대로 정렬하는 정렬 알고리즘이다. 어떤 배열이 있을 때, 배열의 가장 작은 값을 찾아 맨 처음 요소와 위치를 변경하는 작업을 반복하여 정렬을 수행한다. 배열에서 가장 작은 값 1을 찾아 0번째 인덱스 6과 위치를 교환한다. 1번째..

버블 정렬(Bubble Sort) 요약 시간 복잡도 : O(n) = n ^ 2 인접한 두 요소의 대소 관계를 비교하여 반복 교환 시간 복잡도가 느리지만, 코드가 단순하여 구현이 쉬워 자주 사용 요소의 개수가 n개인 배열에서 n - 1회 비교, 교환을 하고 나면 가장 작은 요소가 맨 처음 또는 끝으로 이동 비교, 교환 과정을 패스라고 함 버블 정렬이란 인접한 두 요소의 대소 관계를 비교하여 교환을 반복하는 것을 말한다. 시간 복잡도가 상당히 느리지만, 코드가 단순하여 구현이 쉽기 때문에 자주 사용된다. 원소의 이동이 거품이 수면으로 올라오는 듯한 모습을 보이기 때문에 버블 이라는 이름이 붙었다. 버블 정렬은 정렬을 앞에서 시작할 수도 있고, 뒤부터 시작할 수도 있지만, 요소의 끝부터 확인하고 정렬해야 한다..