IT Study/Java
Java - Quick Sort(퀵 정렬)/ 배열 실습
hhyyyjun
2022. 12. 28. 13:33
| Quick Sort(퀵 정렬)
퀵 정렬은 불안정 정렬에 속하며, 다른 원소와의 비교만으로 정렬을 수행하는 비교 정렬에 속한다.
장점
1) 속도가 빠르다.
2) 추가 메모리 공간을 필요로 하지 않는다.
단점
1) 정렬된 리스트에 대해서는 퀵 정렬의 불균형 분할에 의해 오히려 수행시간이 더 많이 걸린다.
2) 퀵 정렬의 불균형 분할을 방지하기 위하여 피벗을 선택할 때 더욱 리스트를 균등하게 분할할 수 있는 데이터를 선택한다.
EX) 리스트 내의 몇 개의 데이터 중에서 크기순으로 중간 값(medium)을 피벗으로 선택한다.
정렬 과정
1) 리스트 안에 있는 한 요소를 선택한다. 이렇게 고른 원소를 피벗(pivot) 이라고 한다.
2) 피벗을 기준으로 피벗보다 작은 요소들은 모두 피벗의 왼쪽으로 옮겨지고 피벗보다 큰 요소들은 모두 피벗의 오른쪽으로 옮겨진다.
(피벗을 중심으로 왼쪽: 피벗보다 작은 요소들, 오른쪽: 피벗보다 큰 요소들)
3) 피벗을 제외한 왼쪽 리스트와 오른쪽 리스트를 다시 정렬한다.
4) 분할된 부분 리스트에 대하여 순환 호출 을 이용하여 정렬을 반복한다.
5) 부분 리스트에서도 다시 피벗을 정하고 피벗을 기준으로 2개의 부분 리스트로 나누는 과정을 반복한다.
6) 부분 리스트들이 더 이상 분할이 불가능할 때까지 반복한다.
7) 리스트의 크기가 0이나 1이 될 때까지 반복한다.
package class02;
public class Quicksort {
static void quick_sort(int[] data, int start, int end) {
if(start>=end) {
return; //반환 값을 나를 호출한 위치로 전달
// 함수 즉시 종료
}
int pivot=data[start]; //기준값
int L = start+1; //기준값 옆
int H = end; //끝부분
while(true) {
while(pivot>data[L]) {
if(L==end) { //low 포인트가 끝까지 도달했다면
break; //탈출
}
L++; //index 범위를 ++,-- 할 때는 Exception에 유의해야
}
while(pivot<data[H]) {
if(H==start) { //high 포인트가 처음부분에 도달했다면
break; //탈출
}
H--; //index 범위를 --
}
System.out.println("L="+L+", H="+H);
//cross
if(L>=H) { //L이 H보다 크거나 같다면
int tmp = data[start]; //교환 알고리즘
data[start] = data[H];
data[H] = tmp;
for(int i=0;i<data.length;i++) {
System.out.print(data[i]+" ");
}
System.out.println();
System.out.println();
break;
}
int tmp = data[L];
data[L] = data[H];
data[H] = tmp;
for(int i=0;i<data.length;i++) {
System.out.print(data[i]+" ");
}
System.out.println();
System.out.println();
}
quick_sort(data, start, H-1);
quick_sort(data, H+1, end);
}
public static void main(String[] args) {
//재귀함수
int[] data = {5,1,9,10,4,2,7,3,6,8};
System.out.println("Data 초기 값");
for(int i=0;i<data.length;i++) {
System.out.print(data[i]+" ");
}
System.out.println();
System.out.println();
quick_sort(data, 0, data.length-1);
//메서드 시그니처 : 함수 3요소 > input, output, 기능
System.out.println("최종 값");
for(int i=0;i<data.length;i++) {
System.out.print(data[i]+" ");
}
System.out.println();
}
}
| 배열 실습
1. 정수를 입력받아 입력한 정수만큼의 랜덤정수를 저장한 배열생성
2. 랜덤 정수들은 1이상 50이하의 정수들로만 구성, 서로 중복되지 않는다.
3. 배열에 저장된 값들 출력
package test;
import java.util.Random;
import java.util.Scanner;
public class TEST_basic {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
Random rand = new Random();
System.out.print("정수를 입력 해주세요. : ");
int lotto = sc.nextInt(); //정수 입력
//함수
int[] arr = new int[lotto]; //입력한 정수의 크기만큼 배열 생성
//함수
for(int i=0;i<arr.length;i++) { //i가 arr 길이만큼 반복 진행
arr[i] = rand.nextInt(50)+1; //1~50 사이의 랜덤 값 할당
for(int j=0;j<i;j++) { //j가 i만큼 반복
if(arr[i] == arr[j]) { //만약 두 값이 같다면
i--; //i에 1 감소시켜 랜덤값을 재 할당받는다.
}
}
}
//출력할 함수
System.out.print(lotto+"개의 랜덤 값 : ");
for(int i=0;i<arr.length;i++) { //i가 arr 길이만큼 돌아가는 동안
System.out.print(arr[i]+" "); //배열의 각 인덱스 값 출력
}
System.out.println();
}
}
심화
4번의 기능을 수행하는 함수를 정의하고 호출하여 사용
2,3의 기능을 수행하는 함수를 정의하고 호출하여 사용
package test;
import java.util.Random;
import java.util.Scanner;
public class TEST {
//Inout O, Output X
static void f1(int[] data) { //배열 출력하는 함수
System.out.print("랜덤 정수 값 : ");
for(int i=0;i<data.length;i++) { //i가 data 길이만큼 돌아가는 동안
System.out.print(data[i]+" "); //배열의 각 인덱스 값 출력
}
System.out.println();
}
//Input O, Output O
//랜덤 값 할당받는 함수
static int[] f2(int num) { //정수형 배열 반환하는 함수
Random rand = new Random();
int[] lottoNum = new int[num]; //입력한 정수의 크기만큼 배열 생성
for(int i=0;i<lottoNum.length;i++) { //i가 lottoNum 길이만큼 반복 진행
lottoNum[i] = rand.nextInt(50)+1; //1~50 사이의 랜덤 값 할당
for(int j=0;j<i;j++) { //j가 i만큼 반복
if(lottoNum[i] == lottoNum[j]) { //만약 두 값이 같다면
i--; //i에 1 감소시켜 랜덤값을 재 할당받는다.
}
}
}
return lottoNum;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num; //유효 범위
System.out.print("50이하의 정수만을 입력 해주세요 : ");
while(true) { //유효성 검사
num = sc.nextInt(); //정수 입력
if(num>50 || num<1) { //입력된 정수 값이 50 이상이라면
System.out.print("1이상, 50이하의 정수 값만 입력 해주세요. : ");
continue;
}
else {
break;
}
}
int[] lotto = f2(num); //함수 f2 호출
f1(lotto); //함수 f1 호출
}
}
다른 풀이
중복 건에 대해 범위가 정해져있지 않기 때문에 while문을 사용하는 것이 더 좋다
package test;
import java.util.Random;
import java.util.Scanner;
public class TEST {
//Inout O, Output X
static void f1(int[] data) { //배열 출력하는 함수
System.out.print("랜덤 정수 값 : ");
for(int i=0;i<data.length;i++) { //i가 data 길이만큼 돌아가는 동안
System.out.print(data[i]+" "); //배열의 각 인덱스 값 출력
}
System.out.println();
}
//Input O, Output O
//랜덤 값 할당받는 함수
static int[] f2(int num) { //정수형 배열 반환하는 함수
Random rand = new Random();
int[] lottoNum = new int[num]; //입력한 정수의 크기만큼 배열 생성
int i = 0;
while(i<lottoNum.length) {
int randNum = rand.nextInt(50)+1;
//랜덤 수를 우선 생성
// 기존의 배열에 랜덤수가 존재한다면, 다시 위로
// 존재 안하면, 아래로
boolean flag = false;
for(int j=0;j<i;i++) {
if(randNum==lottoNum[j]) {
flag = true;
break;
}
}
if(flag) {
continue;
}//중복 발생하지 않았으므로, 대입
lottoNum[i] = randNum;
i++;
}
return lottoNum; //lottoNum 값 반환
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int num; //유효 범위
System.out.print("50이하의 정수만을 입력 해주세요 : ");
while(true) { //유효성 검사
num = sc.nextInt(); //정수 입력
if(num>50 || num<1) { //입력된 정수 값이 50 이상이라면
System.out.print("1이상, 50이하의 정수 값만 입력 해주세요. : ");
continue;
}
else {
break;
}
}
int[] lotto = f2(num); //함수 f2 호출
f1(lotto); //함수 f1 호출
}
}