코딍코딍
코딩기록
코딍코딍
전체 방문자
오늘
어제
  • 분류 전체보기 (271)
    • 개발 (2)
    • Java (1)
    • 스프링 (28)
    • JPA (11)
    • Git (3)
    • 알고리즘 (160)
      • 백준 (132)
      • 프로그래머스 (8)
      • SWEA (20)
    • 토이 프로젝트 (14)
      • 간단한 Springboot CRUD (1)
      • 게시판 프로젝트 (13)
    • 알고리즘 개념정리 (8)
    • 오류 해결 (13)
    • 보류 (0)
    • AWS (5)
    • 트러블 슈팅 (0)
    • 회고 (3)
    • CS (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

최근 글

티스토리

hELLO · Designed By 정상우.
코딍코딍
알고리즘 개념정리

퀵 정렬

알고리즘 개념정리

퀵 정렬

2022. 8. 1. 12:41

퀵 정렬

기준 데이터를 설정하고 그 기준보다 큰 데이터와 작은 데이터의 위치를 바꾸는 방법이다.
가장 기본적인 퀵 정렬은 첫 번째 데이터를 기준 데이터(Pivot)로 설정한다.

시간 복잡도

  • 평균의 경우: O(NlogN)
  • 최악의 경우: O(N^2)

 

 

동작 과정

0) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '7'이 선택되고
오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '4'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

1) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '9'가 선택되고
오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '2'가 선택된다. 이제 이 두 데이터의 위치를 서로 변경한다.

2) 현재 피벗의 값은 '5'이다. 왼쪽에서부터 '5'보다 큰 데이터를 선택하므로 '6'이 선택되고
오른쪽에서부터 '5'보다 작은 데이터를 선택하므로 '1'이 선택된다. 단, 이처럼위치가 엇갈리는 경우 '피벗'과
'작은 데이터'의 위치를 서로 변경한다.

3) 이제 '5'의 왼쪽에 있는 데이터는 모두 5보다 작고, 오른쪽에 있는 데이터는 모두 '5'보다 크다는
특징이 있다. 이렇게 피벗을 기준으로 데이터 묶음을 나누는 작업을 분할(Divide)이라고 한다.

4) 왼쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

5) 오른쪽에 있는 데이터에 대해서 마찬가지로 정렬을 수행한다.

 

 

구현 코드

public class Main {
    public static void main(String[] args) {
        int n = 10;
        int[] arr = {7, 5, 9, 0, 3, 1, 6, 2, 4, 8};
 
        quickSort(arr, 0, n - 1);
 
        for(int i = 0; i < n; i++) {
            System.out.print(arr[i] + " ");
        }
    }
 
    public static void quickSort(int[] arr, int start, int end) {
        // 원소가 1개인 경우 종료
        if (start >= end) {
            return;
        }
 
        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);
    }
}

'알고리즘 개념정리' 카테고리의 다른 글

이진 탐색  (0) 2022.08.01
삽입 정렬  (0) 2022.08.01
선택 정렬  (0) 2022.07.31
BFS (Breadth-First Search)  (0) 2022.07.30
DFS (Depth-First Search)  (0) 2022.07.30
  • 퀵 정렬
  • 동작 과정
  • 구현 코드
'알고리즘 개념정리' 카테고리의 다른 글
  • 이진 탐색
  • 삽입 정렬
  • 선택 정렬
  • BFS (Breadth-First Search)
코딍코딍
코딍코딍
ㅎ2

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.