[정렬 알고리즘] 퀵 정렬(Quick Sort) in JAVA
안녕하세요(ㆁᴗㆁ✿)
저는 동빈나의 실전 알고리즘을 정독하고있는 독자 중 한명입니다.
JAVA로 구현하시는 분들도 계실꺼고, 영상을 봤는데도 이해가 안되는 분들께 도움이 되고자
부족하지만 여러번 수정 끝에 정리글을 담아보려합니다.
퀵 정렬을 검색 해보면 Pivot(피벗=임의의 기준값)값을 가운데로 설정해두고 정렬하시는 분들을 많이 봤는데
이번 게시글에선 동빈나의 실전 알고리즘 기반으로 항상 첫번째 인덱스를 Pivot값으로 바라보고있기에
첫번째 인덱스 피벗 설정 기반으로 게시글을 작성하도록 하겠습니다.
혹시나 영상을 못보신 분들을 위해 링크남깁니다.
https://www.youtube.com/watch?v=O-O-90zX-U4&list=PLRx0vPvlEmdDHxCvAQS1_6XV4deOwfVrz&index=5
링크로 이동해 강의 영상 보고 오시고 게시글을 읽어주셔도 좋고
시간이 부족하시다면 곧바로 제 게시글을 보셔도 무관합니다!
0. Quick Sort(퀵정렬)에 다뤄볼 주제은 크게 다음과 같습니다.
-
퀵 정렬 방식(알고리즘)으로 푸는 방법
-
퀵 정렬 알고리즘 조건과 순서도
-
퀵 정렬 알고리즘 구현 코드
-
구현 코드 설명 & 이유
-
-
퀵 정렬 알고리즘 특징
+ 이어서 다음 시간에 추가 게시글로 남기겠습니다. (추가 사항입니다.) -
기존 1차 어설픈 보라 코드
-
코드 문제점
- 간과했던 부분
-
-
동빈나 선생님 코드
-
코드 문제점
-
1. 퀵 정렬 방식(알고리즘)으로 푸는 방법
문제 : "5, 7, 1, 2, 4, 6, 8, 9 "를 퀵정렬로 이용해 정렬하세요.
|
상세 풀이 :
|
이해가 안되셨다면... 댓글달아주세요.... 더 이해하기 쉽도록 그림을 그리던지 동영상을찍던지 하겠습니다...!
2. 퀵 정렬 알고리즘 조건과 순서도
위 푸는 방식을 보니 반복되는 내용들과 더불어 조건들이 눈에 보이셨나요?!?!!!?~?!
뭐 조건들을 없는걸 만들어 내는게 아닌 심플하게 옆에 적혀있는 내용들이
곧 조건이고 이러한 조건들이 모여 순서도를 만듭니다.
그럼 조건(요구사항)들을 모아 만든 순서도는 어떨까요?
우선 나와있는 요구사항 토대로 순차적으로 조건 읽어보시면 이미 위에서 푸는 방식에 다 나와있던 내용이였습니다.
2차적으로 추가 예외처리(?)를 나름대로 더 추가 시켜봤습니다. (초록색으로 표시)
순서도는 draw.io로 작성했습니다.
별다른 설치 필요없이 웹에서 바로 볼수있으니 들어가서 크게 보시는걸 추천드립니다.
https://drive.google.com/file/d/14U8yYY-HJugGcKeHNITdD5RoctyX0eta/view?usp=sharing
QuickSort FlowChart
drive.google.com
3. 퀵 정렬 알고리즘 구현 코드
코드는 다음과 같이 구현했습니다.
실행을 직접 곧바로 해보고싶다면 아래 링크로 접속해 Execute 누르시면 바로 확인 가능합니다!
Online Java8 Compiler - Online Java8 Editor - Online Java8 IDE - Java8 Coding Online - Practice Java8 Online - Execute Java8 Onl
www.tutorialspoint.com
import java.util.Arrays;
// 4. Quick sort - Bora
public class QucickTest {
public static void main(String[] args) {
int[] array = { 7, 6, 8, 1, 2, 3, 5, 5, 4 };
quickSort(array, 0, array.length - 1);
System.out.println("result = " + Arrays.toString(array));
}
public static void quickSort(int[] arr, int start, int end) {
if (start >= end) { // 검사할 범위가 1일땐 정렬 완료
return;
}
int pivot = start;
int temp, i, j;
do {
i = start + 1; // i++ (pivot 제외 = +1)
j = end; // j--
// --> 방향으로 피벗값보다 큰값 찾을때 까지
while (arr[i] < arr[pivot]) {
i++;
if (i >= end) {
i = pivot;
}
}
// <-- 방향으로 피벗값보다 작은 값 찾을때 까지
while (arr[j] > arr[pivot]) {
j--;
if (j <= start) {
j = pivot;
}
}
if (i < j) {
// 안 엇갈림 = 자리 바꿈
temp = arr[j];
arr[j] = arr[i];
arr[i] = temp;
} else {
// 엇갈릴 때
if (j != pivot) {
temp = arr[j];
arr[j] = arr[pivot];
arr[pivot] = temp;
}
}
} while (i < j); // 안엇갈렸다면 계속 반복
//엇갈린 경우 바뀐 피벗값 기준으로 정렬 필요
quickSort(arr, start, j - 1);
quickSort(arr, j + 1, end);
}
}GitHub에도 올려놨습니다:D
https://github.com/adbr-dev/algorithm-study/blob/master/04_quickSort.java
adbr-dev/algorithm-study
알고리즘 공부 . Contribute to adbr-dev/algorithm-study development by creating an account on GitHub.
github.com
3-1. 퀵 정렬 알고리즘 구현 코드 추가사항
아래 코드를 보시면 순서도와 다른 부분이 있습니다.
// --> 방향으로 피벗값보다 큰값 찾을때 까지
while (arr[i] < arr[pivot]) {
i++;
if (i >= end) {
i = pivot;
}
}==이 아니라 코드보면 >=로 구현 해놨죠?
이와 같은 경우는 디버깅을 하다가 알게된 재밌는 케이스인데
퀵정렬을 하다보면 엇갈린 경우 작은 값과 자리를 바꾼 뒤
곧바로 피벗 기준으로 좌측(<-)은 피벗보다 작은값들로 우측(->)은 큰값들로 구분되죠?
구분된 다음 다시 정렬할 범위를 줄인채 재귀함수로 호출을 하게되는데
이때 {[0], [1]} 이렇게 사이즈가 2인 Array를 돌리다 보면
- pivot = 0
- i = 1
- j = 1
같은 값을 가졌을 때 검사를 하고 선처리를 i++를 하게되고 end값이랑 같은지 비교하는데
이미 i =2, j=1 인데 i가 커져버린 상태라 ==가 아닌 >=로 구현 해뒀습니다.
그러면 i++처리 전에 검사하면 되지 않나요?
라는 질문이 있을거같아 먼저 대답을 하자면 디버깅 에러터지고 저또한 곧바로 해봤는데
이유는 모르겠지만 구동이 안됩니다..멈춥니다....결과가 안나와요..(◯Δ◯∥)
(제가 Eclipse 환경에서도..coding ground에서도... 이클립스 에러는 디버깅 후에 캡처해서 내용 수정해 올리겠습니다)
4. 퀵 정렬 알고리즘 특징
- 분할 정복 알고리즘
- 피벗값 기준으로 나누어 분할한 뒤 재귀함수와 반복문을 이용해 정렬 진행
- 배열의 원소들을 나누어 계산을 한다는 점에서 더 빠른 정렬 알고리즘 이라 칭함
- 빠른 정렬 알고리즘
- 평균 속도 (시간 복잡도) : O(N*logN)
- 최악의 경우 시간 복잡도 : O(N^2)
- 최악의 경우는 이미 정렬이 되어있을 때
- 시간 복잡도는 O(N^2)에 가깝고, 이 경우 퀵정렬은 비효율적인 알고리즘으로 볼 수 있음
네..^^..! (참 길게도 적었네요..시간도..훌쩍..)
이제 퀵 정렬이 어떻게 돌아가는 구조인지 이해되셨나요?!
직접 어떻게 돌아가는지 작성해보고, 그에 맞춰 순서도를 그려보고, 코드까지 구현해보면 100%이해하시게 될겁니다.
퀵 정렬때문에 하루 반나절은 보낸거같네요...!
실질적인 공부와 코드구현시간 : 티스토리 작성 시간 = 2:8 .......글쓰는데 문제있는거같아...
마지막까지 읽어주셔서 감사합니다.
다음 시간에 제가 처음에 1차적으로 짰던 어설픈 코드와 동빈나 선생님 코드를 그대로 짜면 안되는 이유가 무엇인지에 대해 짧게 다뤄보도록 합니다. (제발짧게..)
그럼 오늘 하루도 즐거운 하루 보내세요! |ω・｀)ノ
추가 관련 자료
+ Prev 알고리즘 공부 루틴