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

Quick Sort 분할 정복 알고리즘이라고도 하며, 특정값을 기준으로 한 배열을 두개의 부분 배열로 나누어 정렬하는 알고리즘이다. pivot을 정하고, 나머지 배열의 양쪽끝에서부터 검사를 한다. 배열의 왼쪽에는 pivot보다 작은 값, 배열의 오른쪽에는 pivot보다 큰 값이 놓이도록, 잘못된 위치에 있는 원소들을 교환한다. 한 검사가 끝나면 적어도 pivot은 제 위치를 찾은 것이고, 나눠진 배열들에 또 퀵 정렬을 적용하고 반복하면 정렬이 완료되게 된다. 이 알고리즘은 while문과 재귀함수로 구현할 수 있다. 배열들을 검사하며 교환하는 while문과 나눠진 두 배열에 퀵 정렬을 적용하는 재귀함수로 이루어진다. 퀵 정렬은 최선의 경우와 최악의 경우에 따라 시간 복잡도가 달라지는데 정렬된 배열을 검사할..

공부/코테 2023. 12. 17. 21:36

이전 1 다음