컴공댕이 공부일지
[ 정렬 알고리즘 ] 퀵 정렬 java 본문
728x90
백준 문제를 풀다가 정렬을 할 떄 내가 아는 버블 정렬이나, 삽입 정렬을 하게되면 시간 초과가 떠서 정렬 알고리즘에 대해 한 번 공부해보았다.
[1] 퀵 정렬
피벗값을 임의로 정해, 이보다 작은 수들은 왼쪽, 큰 수는 오른쪽으로 나눈 후,
나눠진 파트 안에서 또 피벗을 정하고, 작은 수 큰 수 모음으로 나누기.
각각 낱개로 하나씩으로 나눠질때까지 이를 반복.
★참고영상
[자료구조 알고리즘] 퀵정렬(Quicksort)에 대해 알아보고 자바로 구현하기
https://www.youtube.com/watch?v=7BDzle2n47c
퀵 정렬 Java로 구현하기
public class Sort {
public static void QS(int a[], int l, int r) {
int pl=l;
int pr=r;
int p=a[(pl+pr)/2];
do {
while(a[pl]<p) pl++;
while(a[pr]>p) pr--;
if(pl<=pr) {
//스왑
int temp=a[pl];
a[pl]=a[pr];
a[pr]=temp;
pl++;
pr--;
}
} while(pl<=pr);
if(l<pr) QS(a,l,pr);
if(r>pl) QS(a,pl,r);
}
public static void main(String[] args) {
int [] a = {1,4,2,5,6};
int n = a.length;
QS(a, 0, n-1);
for(int i=0; i<n; i++) {
System.out.println(a[i]);
}
}
}
(다른 방법)
public class QuickSort {
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n-1);
System.out.println("Sorted array:");
for (int i=0; i<n; ++i)
System.out.print(arr[i] + " ");
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex-1);
quickSort(arr, pivotIndex+1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j=low; j<high; ++j) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
}
728x90
'CS > 알고리즘' 카테고리의 다른 글
[ 동적프로그래밍 ] 개념 (피보나치, 외발뛰기) (0) | 2024.04.02 |
---|---|
[ 탐욕법 ] 그리디 알고리즘의 사용 조건 및 정당성 증명, 예시 문제 풀이 (1) | 2024.03.28 |
[ 비트마스킹 ] 비트마스킹의 정의와 예제 문제 풀이 ( c++ 백준 11723 집합 ) (0) | 2024.03.12 |
[ 정수론 ] 소수 구하기 - 에라토스테네스의 체, 제곱근 기준 소수 판별, 구현까지 (3) | 2024.03.05 |
[ 정수론 ] 최대공약수 구하기 - 유클리드 호제법 (0) | 2024.03.02 |
Comments