[Java] Ch.19 정렬 알고리즘 만들기

버블 정렬 알고리즘

1. 인접한 요소끼리 비교하여 더 작은 값을 앞으로, 큰 값을 뒤로 저장
2. 1번 과정을 마지막 원소까지 반복
3. 더 이상 자리를 교환하지 않을 때까지 1번, 2번 반복

 

import java.util.Scanner;

public class BubbleSort
{
	public static void getNumber(int[] num)
	{
		Scanner sc = new Scanner(System.in);
		System.out.println("10개의 정수를 무작위로 입력하세요.");
		
		for(int i = 0; i < num.length; i++)
		{
			num[i] = sc.nextInt();
		}
	}
	
	public static void bubbleSort(int[] num)
	{
		for(int i = 0; i < num.length; i++)
		{
			for(int j = 0; j < num.length - i - 1; j++)
			{
				if(num[j] > num[j + 1])
				{
					int tmp = num[j];
					num[j] = num[j+1];
					num[j+1] = tmp;
				}
			}
		}
	}
	
	public static void main(String[] args)
	{
		int[] num = new int[10];
		
		getNumber(num);
		bubbleSort(num);

		for(int i = 0; i < num.length; i++)
		{
			System.out.print(num[i] + " ");
		}
		System.out.println();
	}

}

 

 

삽입 정렬 알고리즘

배열의 모든 요소를 앞에서부터 차례대로 이미 정렬된 배열 부분과 비교하여, 적절한 자신의 위치를 찾아 삽입하는 정렬

1. 인덱스 0은 정렬되어 있다고 가정함, 그래서 현 위치는 인덱스 1부터 시작
2. 현 인덱스의 값과 바로 앞 인덱스의 값을 비교하여 더 작은 값을 앞으로, 큰 값을 뒤로 저장
3. 2번 과정을 반복하다가 바로 앞에 있는 값이 더 작다면 현 위치를 뒤로 옮김(인덱스 +1 위치로)
4. 마지막 인덱스까지 2번, 3번 반복

 

public class InsertSort
{
	public static void insertSort(int[] num)
	{
		// 삽입 정렬 로직 구현
		int size = num.length;
		int temp = 0;
		int j = 0;
		
		for (int i = 1; i < size; i++)
		{
			temp = num[i];
			for(j = i - 1; j >= 0 && temp < num[j]; j--)
			{
				num[j+1] = num[j];
			}
			num[j+1] = temp;
		}
	}
	
	public static void main(String[] args)
	{
		int num[] = {5, 3, 1, 4, 2};
		insertSort(num);
		
		// 출력 로직 구현
		for(int i = 0; i < num.length; i++)
		{
			System.out.print(num[i] + " ");
		}
		System.out.println();
	}

}