[ java ] 정렬 알고리즘
페이지 정보
작성자 웹지기 댓글 0건 조회 1,571회 작성일 20-12-16 09:26본문
버블 정렬(Bubble Sort)
- 치환할 내용이 발생 하면 바로 치환
① 다른 정렬에 비해 속도가 느리다.
② 삽입 정렬은 두 번째 인덱스부터 시작한다. 현재 인덱스 값과, 바로 이전의 인덱스 값을 비교
③ 현재 인덱스가 더 크면, 교환하지 않고 다음 두 연속된 배열값을 비교
④ 이를 전체배열의 크기 현재까지 순환하는 바퀴 수 만큼 반복
import java.util.Arrays;
public class Exam01_버블정렬 {
public static void main(String[] args) {
//버블 정렬
int[] arr = {10, 9, 8, 7, 5};
//오름차순으로 정렬
for(int j=arr.length-1; j>0; j--) {
for(int i=0; i<j; i++) {
if(arr[i] > arr[i+1]) { //큰수를 오른쪽으로 보내면서 저장
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
//정렬 과정 확인
System.out.println(Arrays.toString(arr));
}
System.out.println();
}
for(int i : arr) {
System.out.print(i+"\t");
}
System.out.println();
//내림차순으로 정렬
for(int j=arr.length-1; j>0; j--) {
for(int i=0; i<j; i++) {
if(arr[i] < arr[i+1]) { //작은수를 오른쪽으로 보내면서 저장
int temp = arr[i];
arr[i] = arr[i+1];
arr[i+1] = temp;
}
//정렬 과정 확인
System.out.println(Arrays.toString(arr));
}
System.out.println();
}
for(int i : arr) {
System.out.print(i+"\t");
}
}
}
삽입 정렬(Insertion Sort)
- 현재위치에서, 그 이하의 배열들을 비교하여 자신이 들어갈 위치를 찾아, 그 위치에 삽입하는 정렬
① 삽입 정렬은 두번째 인덱스부터 시작. 현재 인덱스는 별도의 변수에 저장해주고, 비교 인덱스를 현재 인덱스 -1로 잡는다.
② 별도로 저장해 둔 삽입을 위한 변수와 빅 인덱스의 배열 값을 비교
③ 삽입 변수의 값이 더 작으면 현재 인덱스로 비교 인덱스의 값을 저장해주고 비교 인덱스를 -1하여 비교를 반복
④ 만약 삽입 변수가 더 크면 비교 인덱스+1에 삽입 변수를 저장
선택 정렬(Selection Sort)
- 현재 위치에 들어갈 값을 찾아 정렬하는 배열 - idx값만을 찾아놔서 나중에 치환
① 정렬 되지 않은 인덱스의 맨 앞에서 부터, 이를 포함한 그 이후의 배열값 중 가장 작은 값을 찾아간다.
(정렬되지 않은 인덱스의 맨 앞은, 초기 입력에서는 배열의 시작위치일 것이다.)
② 가장 작은 값을 찾으면, 그 값을 현재 인덱스의 값과 바꿔준다.
③ 다음 인덱스에서 위 과정을 반복
import java.util.Arrays;
import java.util.Random;
public class Exam05_선택정렬2 {
public static void main(String[] args) {
Random r = new Random();
int[] arr = new int[10];
for(int i=0; i<arr.length; i++) {
arr[i] = r.nextInt(20)+1;
}
System.out.println(Arrays.toString(arr));
System.out.println();
for(int j=0; j<arr.length; j++) {
int minIdx = j;
for(int i=j+1; i<arr.length; i++) {
//가장작은 index 찾기
if(arr[minIdx] > arr[i]) {
minIdx = i;
}
System.out.println(Arrays.toString(arr));
}
//idx의 값만을 가져와서 치환을한다.
int temp = arr[j];
arr[j] = arr[minIdx];
arr[minIdx] = temp;
System.out.println();
}
System.out.println(Arrays.toString(arr));
}
}
합병 정렬(Merge Sort)
- 분할 정복(Divide and conquer)방식으로 설계된 알고리즘.
- 분할 정복은 큰 문제를 반으로 쪼개 문제를 해결해 나가는 방식으로, 분할은 배열의 크기가 1보다 작거나 같을 때 까지 반복
- 분할 과정
① 현재 배열을 반으로 쪼갬. 배열의 시작 위치과, 종료 위치를 입력받아 둘을 더한 수 2를 나눠 그 위치를 기준으로 나눈다.
② 이를 쪼객 배열의 크키가 0이거나 1일 때 까지 반복한다.
- 합변 과정
① 두 배열 A, B의 크기를 비교한다. 각각의 배열의 현재 인덱스를 i,j로 가정
② i 에는 A배열의 시작 인덱스를 저장. j에는 B 배열의 시작 주소를 저장
③ A[i]와 B[i]를 비교. 오름차순의 경우 이중에 작은 값을 새 배열 C에 저장
A[i]가 더 컸다면 A[i]의 값을 배열 C에 저장해주고, i값을 하나 증가
④ 이를 i나 j 둘중 하나가 각자 배열의 끝에 도달 할 때까지 반복
⑤ 끝까지 저장을 못한 배열의 값을, 순서대로 전부C에 저장
⑥ C 배열을 원래의 배열에 저장
댓글목록
등록된 댓글이 없습니다.