정렬 알고리즘.
기초적인 방법 : 버블정렬, 선택정렬, 삽입정렬
***Array.sort()함수는 듀얼피봇 퀵정렬이라는 방식을 사용함. 가장 빠르고 효율적이지만 너무 어려운 내용이라 그냥 넘어간다.
버블정렬
가장 비효율적이지만 만들기 쉽고 간단해서 많이 쓰인다.
인덱스 0 부터 인덱스 끝까지 대/소를 비교하고, 만약 상대가 더 크거나 작다면 자신과 데이터를 교환하는 방식. 교환하고도 계속 비교 하지만, 이때도 기준은 인덱스다.
예를 들어보자.
배열 a[ ]를 오름차순으로 정리하고 있다.
a[2]의 값을 a[3], a[4] ... a[n]까지 계속 비교하는 도중, a[10]이 자신보다 더 작다는 것을 발견했다.
그럼 이어서 a[2]의 데이터와 a[10]의 데이터를 맞교환한다.
그리고 이어서 바뀐 a[2]를 계속해서 a[11]과 비교한다. 만약 이후에도 자신보다 더 작은 데이터를 발견한다면, 그 데이터와 자신의 데이터를 교환한다.
public class ex61 {
public static void main(String[] args) {
//정렬 알고리즘
//대표적인 방법 : 버블정렬, 선택정렬, 삽입정렬
//Arrays.sort()함수 안에도 정렬알고리즘 - 듀얼피봇 퀵정렬
//1. 버블정렬
// 모든 자릿수를 오른쪽자리와 비교해서 맞교환(치환)하는 방식
int[] numbers = { 9, 8, 1, 3, 2 };
//연습문제 42 - 2중 반복문
//모든 자릿수를 비교해보자.
//출력: 9:8 9:1 9:3 9:2
// 8:1 8:3 8:2
// 1:3 1:2
// 3:2
for(int i=0; i<numbers.length; i++){
for(int j=i+1; j<numbers.length; j++){
System.out.print( numbers[i] + ":" );
System.out.print( numbers[j] + " " );
}
System.out.println();
}
//연습문제 43
//버블 정렬-오름차순 을 구현해보자.
//모든 자릿수를 비교해서, 오른쪽값이 더 작으면
//치환한다.(자리 이동)
//정렬된 결과를 출력하시오.
for(int i=0; i<numbers.length; i++){
for(int j=i+1; j<numbers.length; j++){
//i: 왼쪽값 j: 오른쪽값
//오름차순은 맨 앞에 제일 작은 값이 위치.
if( numbers[j] < numbers[i] ){
//내리차순 정렬은 부호만 반대로 하면 됨.
int temp = numbers[j];
numbers[j] = numbers[i];
numbers[i] = temp;
}
}
}
for( int num : numbers ){
System.out.println( num );
}
}
}
2. 선택정렬
최대 최소값 찾기와 비슷한 방법을 사용한다.
1. 새로운 변수(minIndex)를 만들아 for문의 i값을 할당한다.
2. 다시 for문을 사용해 a[ i ] 보다 작은 변수를 찾는다.
3. 더 작은 값을 발견하면, 그 인덱스 번호를 이전에 설정한 변수(minIndex)에 저장한다.
4. a[ i ] 의 값을 새로운 변수(tmep)에 저장하고, a[ i ]보다 작은 a[ f ]의 값을 a[ i ]에 넣는다.
5. a[minIndx]에 temp의 값을 다시 할당한다.
public class ex62 {
public static void main(String[] args) {
//2. 선택정렬
// 인덱스변수 minIndex에 최소값 인덱스를 설정하고,
// minIndex를 이용해서 맞교환 하는 방식.
int[] nums = { 9, 8, 1, 3, 2 };
int minIndex;
for(int i=0; i<nums.length-1; i++){
minIndex = i;
System.out.println("minIdx:"+minIndex);
for(int j=i+1; j<nums.length; j++){
if( nums[j] < nums[minIndex] ){
//더 작은 값을 발견! => minIndex값을 변경!
minIndex = j;
}
}
//minIndex값을 이용해서 맞교환한다.
int temp = nums[i];
nums[i] = nums[minIndex];
nums[minIndex] = temp;
}
for( int num : nums )
System.out.println( num );
}
}
3. 삽입정렬
인덱스 번호 1(두번째 데이터) 부터 비교를 시작한다.
자신보다 왼쪽의 숫자(인덱스 번호 0) 과 자신을 비교한 뒤, 더 작은 값이면 맞교환한다.
이후 인덱스 번호를 2로 올려서 다시 자신의 왼쪽 데이터들(인덱스 번호가 더 낮은 데이터들) 과 자신을 비교한뒤, 맞교환한다.
교환할 값을 가진 key값을 이용한다.
public class ex63 {
public static void main(String[] args) {
//3. 삽입 정렬
// 인덱스 1(두번째)부터 정렬을 시작하고,
// 자기보다 왼쪽에 있는 값들과 비교하여,
// 더 작은 값이면 맞교환한다.
// 교환할 값을 가진 key변수를 이용함.
int[] nums = { 9, 8, 1, 3, 2 };
int key;
for(int i=1; i<nums.length; i++){
key = nums[i]; //8
int j = i - 1;
while( j >= 0 && nums[j] > key ){
nums[ j + 1 ] = nums[j]; //9 9 1 3 2
j--; //증감문
}
nums[ j + 1 ] = key; //8 9 1 3 2
}
for( int num : nums )
System.out.println( num );
}
}
'공부 > java' 카테고리의 다른 글
자바(java)의 싱글톤 패턴 (1) | 2023.01.23 |
---|---|
자바(java)의 오버로딩(Overloading) (0) | 2023.01.23 |
자바(java)의 열거형 표현 (0) | 2023.01.23 |
자바(java)의 배열 (0) | 2023.01.23 |
자바(java)의 반복문: for, while (1) | 2023.01.23 |