Java 정렬 알고리즘

정렬 알고리즘

: 원소들을 일정한 순서대로 열거하는 알고리즘

버블 정렬

: 두 인접한 원소를 비교하여 정렬하는 방법

장점
- 인접한 값만 계속해서 비교하는 방식으로 구현이 쉽다. 코드가 직관적이다

단점
- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 요소와 교환되어야 한다.
- 특정 요소가 최종 정렬 결과에 맞는 위치에 있더라도 교환되는 일이 일어날 수 있다.

=> 구현이 단순하지만 느림

코드

package 버블정렬;

import java.util.Arrays;

public class 버블정렬_오름차순 {
	public static void main(String[] args) {

		int[] arr = {7,4,5,1,3};
		
		System.out.println("정렬 전 : " + Arrays.toString(arr));
		
		/*
		for (int i = 0; i < arr.length - 1; i++) {
			if(arr[i] > arr[i+1]) { //교환
				int temp; //임시공간
				temp = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = temp;
			}
		}
		
		System.out.println("1회차 : " + Arrays.toString(arr));
		
		for (int i = 0; i < arr.length - 2; i++) {
			if(arr[i] > arr[i+1]) { //교환
				int temp; //임시공간
				temp = arr[i];
				arr[i] = arr[i+1];
				arr[i+1] = temp;
			}
		}
		
		System.out.println("2회차 : " + Arrays.toString(arr));
		*/
			
		for(int j = 1;j <= 4;j++) {
			int cnt = 0; //현재 회차에서 교환된 횟수 
			
			for (int i = 0; i < arr.length - j; i++) {
				if(arr[i] > arr[i+1]) { //교환
					int temp; //임시공간
					temp = arr[i];
					arr[i] = arr[i+1];
					arr[i+1] = temp;	
					cnt++;
				}
			}	
			if(cnt == 0) {
				System.out.println("이미 정렬 완료");
				break;
			}
			System.out.println(j + "회차 : " + Arrays.toString(arr));
		}
	}
}

선택 정렬

장점
- 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적기에 교환이 많이 이루어져야 하는 상태에서 효율적(내림차순 정렬되어 있는 자료를 오름차순으로 재정렬할 때)

단점
- 정렬을 위한 비교 횟수가 많으며 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 처리 속도가 느림

=> 비교 횟수는 많고 교환 횟수는 적음

package 선택정렬;

import java.util.Arrays;

public class 선택정렬_오름차순 {
	public static void main(String[] args) {
		
		int[] arr = {7,4,5,1,3};
		
		System.out.println("정렬 전 = " + Arrays.toString(arr));
		
		int min, temp;
		
		
		for (int i = 0; i < arr.length - 1; i++) {
			min = i;
			for (int j = i+1; j < arr.length; j++) {
				if(arr[min] > arr[j]) {
					min = j;
				}
			}
			
			temp = arr[min];
			arr[min] = arr[i];
			arr[i] = temp;
			System.out.println((i+1)+"번째 정렬 = " + Arrays.toString(arr));
		}
	}
}

검색 알고리즘

: 특정 원소를 검색하는 알고리즘

순차 검색

: 가장 단순한 검색 방법으로 원소의 정렬이 필요없다.
하지만 리스트 길이가 길면 비효율적

이진 검색

: 리스트 중간 값을 정해 크고 작음을 비교해 검색하는 알고리즘
정렬된 리스트에 사용할 수 있다

코드

package 이진탐색;

public class 이진탐색 {
	public static void main(String[] args) {
		int[] arr = {1,7,16,25,30,33,41,66,78,90};
		
		int num = 78; //우리가 찾고 싶은 숫자
		
		int lowIndex = 0;
		int highIndex = arr.length - 1;
		
		while(true) {
			int centerIndex = (lowIndex+highIndex)/2;
			
			if(arr[centerIndex] == num) {
				System.out.println(num + "은 " + centerIndex + "번째 숫자입니다");
				break;
			}else if(arr[centerIndex]<num) {
				lowIndex = centerIndex + 1;
			}else { //arr[centerIndex]>num
				highIndex = centerIndex - 1;
			}
		}
	}
}