(JAVA/Python)QuickSort 알고리즘

과제가 있어 QuickSort 알고리즘을 자바로 구현해봤다.

 

import java.util.InputMismatchException;
import java.util.Scanner;

public class test3 {

    public static void quickSort(int[]arr, int start, int end) {
        if(start>=end) {                                // 퀵정렬 알고리즘
            return;                                     // 원소 1개면 종료
        }
        int pivot = start;                                // 리스트 첫번째를 기준점으로 가짐
        int left = start+1;                             // 왼쪽값 설정
        int right=end;                                  // 우측값 설정
        while(left<=right) {
            while(left<=end&&arr[left]<=arr[pivot]) {
                left++;                                  // 큰 데이터 찾을 떄 까지 반복
            }
            while(right>start&&arr[right]>=arr[pivot]) {
                right--;                                 // 작은 데이터 찾을 떄 까지 반복
            }

            if(left>right) {                             // 찾는 값이 엇갈렸을때 즉 찾는 값이 서로 지나 쳤을때 
                int temp = arr[pivot];					 
                arr[pivot] = arr[right];
                arr[right] = temp;
            }else {
                int temp = arr[left];
                arr[left]= arr[right];
                arr[right]=temp;
            }
            
        }
        quickSort(arr, start, right-1);             // 분할이후 왼쪽에서 정렬수행
        quickSort(arr, right+1,end);               // 분할이후 오른쪽에서 정렬 수행
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int[] arr = {10,1,9,2,8,3,7,4,6,5};
        int pivot = 0;

        quickSort(arr,0,arr.length-1);
        System.out.print("결과 : ");
        for (int i = 0; i < arr.length-1; i++) {
            System.out.print("" + arr[i] + ", ");
            if (i == 8 ){
                System.out.print(arr[9]);
            }
        }
    }
}
// https://www.youtube.com/watch?v=O-O-90zX-U4

 

 

퀵 정렬이란 기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.

 

가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터로 설정한다.

 

왼쪽에서부터는 기준값보다 큰값/ 오른쪽에서부터는 기준값보다 작은값을 구해서 위치를 바꿔준다.

 

그러다 위치가 엇갈린경우 > 작은값과 피벗값을 바꿔준다 

 

바뀐 피벗값 기준으로 왼쪽은 피벗보다 작은값 오른쪽은 피벗보다 큰 값으로 나뉜다.

 

바뀐 배열집합으로 왼쪽 , 오른쪽 정렬을 수행한다.

 

빅오는 피벗의 값의 따라 다르다,  평균의 경우 o(NlogN) 최악의 경우 o(N^2) 이다.

 

def quick_sort(array, start, end):
    if start >= end: return # 원소가 1개인 경우
    pivot = start # 피벗은 첫 요소
    left, right = start + 1, end

    while left <= right:
        # 피벗보다 작은 데이터를 찾을 때까지 반복
        while left <= end and array[left] <= array[pivot]:
            left += 1
        # 피벗보다 큰 데이터를 찾을 때까지 반복
        while right > start and array[right] >= array[pivot]:
            right -= 1
        if left > right: # 엇갈린 경우
            array[right], array[pivot] = array[pivot], array[right]
        else: # 엇갈리지 않은 경우
            array[right], array[left] = array[left], array[right]
    # 분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 정렬 수행
    quick_sort(array, start, right - 1)
    quick_sort(array, right + 1, end)

array = [10,9,8,7,6,5,4,3,2,1]
quick_sort(array,0,len(array)-1)
print(array)

 

 

 

참고:https://freedeveloper.tistory.com/377