[자료구조와 알고리즘] 정렬 알고리즘, 탐색 알고리즘 (2023.04.04)

🎈 정렬 알고리즘

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

📖 삽입정렬 

특정한 데이터를 적절한 위치에 삽입하는 정렬

데이터가 거의 정렬 되어 있을 때 효율적

 

📖 병합정렬

주어진 자료를 잘게 쪼갠 뒤 합치는 과정에서 정렬

 

📖 퀵정렬 

기준 키(pivot)를 기준으로 작거나 같은값을 지닌 데이터는 앞으로, 큰 값을 지닌 데이터는 뒤로 가도록 하여 데이터를 분리해가며 정렬

왼쪽에서 시작한 키는 기준키보다 크면, 오른쪽에서 시작한 키는 기준키보다 작으면 멈춤

두 개의 자리를 바꿈

두 개의 커서가 만나면 왼쪽으로는 기준키보다 작은 값만, 오른쪽에는 기준키보다 큰 값만 남음

 

📖 버블정렬

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

한 턴만 끝나도 가장 큰 숫자가 제일 뒤에 있음

시작은 인덱스 0, 1부터 > 1, 2 > 2, 3 > ... > n-1, n까지 확인   ---- 1회차

0,1 > 1,2 > 2,3 > ... >n-2, n-1 ----- 2회차

...

최대 n-1회차까지 진행

 

장점

- 인접한 값만 계속해서 비교하는 방식으로 구현이 쉽다. >> 치환이 많이 이루어진다. 

- 코드가 직관적이다.

- 중간에 멈출 수 있음

 

단점

- 하나의 요소가 가장 왼쪽에서 가장 오른쪽으로 이동하려면 배열의 모든 요소와 교환 되어야 함

- 특정 요소가 최종 정렬 결과에 맞는 위치에 있더라도 교환되는 일이 일어날 수 있음

 

즉, 구현이 단순하지만 느리다. 

 

package 알고리즘;

import java.util.Arrays;

public class Ex01버블정렬_내림차순 {

	public static void main(String[] args) {
		//다음 배열을 버블 정렬 알고리즘을 이용하여 내림차순으로 정렬한 후 결과와 교환 횟수 출력
		
		int[] arr = {6,8,2,1,4,3};
		int cnt = 0;
		boolean sw = true;
		
		for(int k = 0 ; k < arr.length - 1 ; k++) {
			sw = true;
			for(int i = 0 ; i < arr.length - k - 1 ; i++) {
				if(arr[i] < arr[i+1]) {
					int temp = arr[i];
					arr[i] = arr[i+1];
					arr[i+1] = temp;
					sw = false;
				}
			}
			if(sw) {
				break;
			}
			
			System.out.println(k+1 + "회차 : " + Arrays.toString(arr));
		}
	}
}

 

📖 선택 정렬

가장 큰 원소 또는 작은 원소를 찾아 주어진 위치를 교체해 나가는 작업

 

가장 작은 수가 있는 인덱스를 기억하는 변수 필요

0번 인덱스와 1~n-1번 인덱스까지 하나하나 비교해가며 가장 작은 숫자의 인덱스를 기억해두었다가, 위치 교환

1번 인덱스와 2~n-1번 인덱스까지 하나하나 비교해가면 가장 작은 숫자의 인덱스를 기억해두었다가, 위치 교환

최대 n-1회차까지 진행

 

회차의 마지막에만 치환. 바꾸는게 적다. -> 이를 위해 인덱스 번호를 기억한다. 

중간에 멈출 수 없음. 끝까지 봐야한다. 

 

장점

- 정렬을 위한 비교 횟수는 많으나 교환 횟수가 적기에 교환이 많이 이루어져야 하는 상태에서 효율적

단점

- 이미 정렬된 상태에서 소수의 자료가 추가되면 재정렬할 때 처리 속도가 느림

 

package 알고리즘;

import java.util.Arrays;

public class Ex03선택정렬알고리즘_내림차순 {

	public static void main(String[] args) {
		
		int[] arr = {6,8,2,1,4,3};
		int index;
		for(int i = 0 ; i < arr.length - 1 ; i++) {
			index = i; //index는 가장 큰 수의 인덱스 번호를 저장하는 변수
			for(int j = index + 1 ; j < arr.length ; j++) {
				if(arr[j] > arr[index]) {
					index = j;
				}
			}
			int temp = arr[i];
			arr[i] = arr[index];
			arr[index] = temp;
			
			System.out.println(i+1 + "회차 : " + Arrays.toString(arr));
		}

	}

}

 

 

🎈 검색 알고리즘 

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

 

📖 순차검색

가장 단순한 검색 방법으로 원소의 정렬이 필요없다. 

하지만 리스트 길이가 길면 비효율적

처음부터 끝까지 순차적으로 비교 

 

package 알고리즘;

public class Ex05순차검색알고리즘 {

	public static void main(String[] args) {
		
		int num = 78;
		
		int[] arr = {13,35,15,11,26,72,78,13,61,90};
		
		for(int i = 0 ; i < arr.length - 1 ; i++) {
			if(num == arr[i]) {
				System.out.println(i);
				break;
			}
		}

	}

}

 

📖 이진검색

리스트의 중간 값을 정해 크고 작음을 비교해 검색하는 알고리즘

정렬된 리스트에서만 사용할 수 있음

 

첫번째 인덱스와 마지막 인덱스 사이 중간 번호 인덱스와 찾고자 하는 수와 비교

찾고자 하는 수가 중간 번호 인덱스의 값보다 크면 중간값 이후의 값만 확인

첫 인덱스와 마지막 인덱스 사이 중간 인덱스의 값과 찾고자 하는 수와 비교

찾고자 하는 수보다 중간값보다 크면 중간값 이후의 값 확인 

위의 상황을 반복. 중간번호 인덱스의 값이 찾고자 하는 수와 같을 때까지. 

 

package 알고리즘;

public class Ex06이진검색알고리즘 {

	public static void main(String[] args) {
		
		//이진검색알고리즘
		//변수 3개를 사용해서 데이터를 검색
		//lowIndex, highIndex, middleIndex
		//장점 : 시간복잡도가 1/2로 빠른 탐색 속도를 가지고 있음!
		//단점 : 검색 알고리즘 상 정렬된 리스트에서만 사용할 수 있음!
		
		int[] arr = {1,7,16,25,30,33,41,66,78,90};
		
		//lowIndex : 최소 index 값
		int lowIndex = 0;
		
		//highIndex : 최대 index 값
		int highIndex = arr.length - 1;

		int num = 78; //찾고자 하는 수
		
		while(true) {
			//middleIndex 초기화
			int middleIndex = (lowIndex + highIndex) / 2 ;
			
			if(arr[middleIndex] == num) { //7
				System.out.println("인덱스 번호 : " + middleIndex);
				break;
			}else {
				if(arr[middleIndex] > num) {
					highIndex = middleIndex - 1;
				}else {
					lowIndex = middleIndex + 1; 
				}
			}
		}
		

	}

}