JAVA 알고리즘 - Quick 정렬 구현하기

업무 중, 퀵정렬을 사용할 경우가 생겨서 리마인드 할 겸, 정리해서 작성해 보았다.

매일 매일 사용하면 까먹지라도 않겠지... 리마인드 하면서 머리속에 세뇌시켜야지..

  1. public class QuickSortRemind {
  2. public static void main(String[] args) {
  3. // test 데이터
  4. int[] arr = {22,5,7,33,4,55,88,22,553,67,2,7,9,10};
  5. // quickSort 함수 호출
  6. // 0부터 배열 length 까지 탐색
  7. quickSort(arr, 0, arr.length-1);
  8. // 출력
  9. for ( int a : arr ) {
  10. System.out.println(a);
  11. }
  12. }
  13. static void quickSort(int[] arr, int start, int end) {
  14. // 퀵소트는 중간값에서 파티션을 양쪽으로 나눠서 값을 비교하고 swap 한다. ( 파티션1 | 피봇(중간값) | 파티션2 )
  15. // partition 의 return 값 part는 파티션1의 마지막 end 값
  16. // partition 의 return 값 part는 파티션2의 첫번째 start 값
  17. int part = partition(arr, start, end); // 중간 값 index 도출
  18. // start 값과 파티션1의 마지막 end 값으로 비교
  19. // start는 0부터 시작~
  20. if( start < part-1 ) {
  21. // 재귀함수 호출
  22. quickSort( arr, start, part-1 );
  23. }
  24. // 마지막 end 값과 파티션2의 첫번째 start 값으로 비교
  25. if ( end > part ) {
  26. // 재귀함수 호출
  27. quickSort( arr, part, end );
  28. }
  29. }
  30. static int partition(int[] arr, int start, int end) {
  31. // start + end / 2로 중간값 인덱스를 찾을 수 있다.
  32. int pivot = arr[ (start+end) / 2]; // 중간 값 pivot 추출
  33. // start 시작값이 end 값보다 작거나 같을 때까지 loop
  34. while ( start <= end ) {
  35. // 피봇 ( 중간값 )이 start 인덱스 배열값보다 작으면 swap 할 필요가 없으니 start 값을 ++ 한다.
  36. while ( arr[start] < pivot ) {
  37. start++;
  38. }
  39. // 피봇 값이 end 인덱스 배열의 값보다 크면 swap 할 필요가 없으니 끝에서부터 -- 한다.
  40. while ( arr[end] > pivot ) {
  41. end--;
  42. }
  43. // start가 end 값보다 작거나 같을 때.
  44. if ( start <= end ) {
  45. // swap 진행
  46. // why ? -> start 값과 end 값은 위 while 문에서 변경해야 할 인덱스 값으로 삽입된다.
  47. // start end 값 비교가 필요 없을 경우 while문을 종료한다.
  48. swap(arr, start, end);
  49. start++;
  50. end--;
  51. }
  52. }
  53. return start;
  54. }
  55. // 배열 스왑
  56. static void swap (int[] arr, int i, int j) {
  57. int tmp = arr[i];
  58. arr[i] = arr[j];
  59. arr[j] = tmp;
  60. }
  61. }



* 파트너스 활동을 통해 일정액의 수수료를 제공받을 수 있음
작성자 소개
최찬희 프로필
WrapUp 블로거

최찬희

반려견을 좋아하고, 차를 좋아하고, 여행을 좋아하고, 맛집을 찾아 즐기는 웹 개발자 입니다^^

댓글작성

작성자의 다른 포스팅