[알고리즘] 1. 정렬

1. 정렬 알고리즘

버블 정렬	데이터를 인접 요소끼리 비교해, swap 연산을 수행하면서 정렬
선택 정렬	대상에서 크거나 작은 데이터를 찾고, 선택을 반복하면서 정렬
삽입 정렬	대상을 선택해 정렬된 영역에서 선택 데이터의 위치를 찾아 삽입하면서 정렬
퀵 정렬	pivot 값을 선정해 해당 값을 기준으로 정렬
병합 정렬	이미 정렬된 부분들을 효율적으로 병합해 전체를 정렬
기수 정렬	데이터의 자릿수를 바탕으로 비교해 정렬

---

2. 정렬 알고리즘 구현

 

(1) 버블 정렬 : 루프를 돌면서 인접한 데이터간 swap 연산으로 정렬

N(정렬할 수 개수)
A(정렬할 배열 선언)
for(i : 0 ~ N - 1)
 {
  for(j : 0 ~ N - 1 - i)
  {
   현재 A 배열의 값보다 1칸 오른쪽 배열의 값이 더 작으면 두 수 바꾸기)
  }
 }
A 배열 출력

 

 

package sorting.ch04;

import java.util.Scanner;

public class sorting01_q15_sol {
	public static void main(String[] args) {
		Scanner kb = new Scanner(System.in);
		int n = kb.nextInt();
		int[] arr = new int[n];
		for(int i = 0 ;i<n;i++) {
			arr[i]=kb.nextInt();
		}
		for(int i=0;i<n-1; i++) {
        //비교를 자기 자신보다 +1한 수와 비교하기 때문에 n이 아니라 n+1이어도 가능하다.
			for(int j=0;j<n-1-i;j++) {
				if(arr[j]>arr[j+1]) {
					int tmp= arr[j];
					arr[j]=arr[j+1];
					arr[j+1]=tmp;
				}
			}
		}
		for(int i=0;i<n;i++) System.out.println(arr[i]);
	}

}

---

 

(2) 선택 정렬 : 최솟값 또는 최댓값을 찾고, 남은 정렬 부분의 가장 앞의 데이터와 swap해 정렬

str(정렬할 수)
A(자릿수별로 구분해 저장한 배열)
for(str의 길이만큼 반복하기) {
 A 배열 저장 -> str.substring 사용하기
}

for(i : 0 ~ str의 길이만큼 반복하기){
 for(j : i + 1 ~ str의 길이만큼 반복하기) {
  현재 범위에서 max값 찾기
  }
  현재 i의 값과 max값 중 max값이 더 크면 swap 수행하기
 }
 A 배열 출력하기

 

	public void solution(String str, int[] arr) {
		for (int i = 0; i < str.length(); i++) {
			int max = i;
			for (int j = i + 1; j < str.length(); j++) {
				if (arr[j] > arr[max])
					max = j;
                    //최댓값 찾기
			}
			if (arr[i] < arr[max]) {
            //현재 swap 대상 위치가 최댓값이 아니면 swap
				int tmp = arr[i];
				arr[i] = arr[max];
				arr[max] = tmp;
			}
		}
		for (int x : arr)
			System.out.print(x);

	}

 

+) 내장함수 이용

	public int solution(int n) {
		int answer=0;
		String tmp = Integer.toString(n);
		char[] arr =tmp.toCharArray();
		Character [] arr2 =new Character[arr.length];
		for(int i=0;i<arr.length;i++) arr2[i]=arr[i];
		Arrays.sort(arr2, Collections.reverseOrder());
		for(int i=0;i<arr.length;i++) arr[i]=arr2[i];

		tmp=String.valueOf(arr);
		answer=Integer.parseInt(tmp);
		
		return answer;
	}

---

(3) 삽입 정렬 :  선택 데이터를 현재 정렬된 데이터 범위 내에서 적절한 위치에 삽입해가면서 정렬

N（사람 수）
A（자릿수별로 구분해 저장한 배열）
S（A 합 배열: 각 사람이 인출을 완료하는 데 필요한 시간을 저장하기）
for（N만큼 반복하기） {
A 배열 저장하기
}
for（i: N만큼 반복하기） {
    for（j: i - 1 ~ 0까지 뒤에서부터 반복하기） {
    현재 범위에서 삽입 위치 찾기
    }
    for（j: i ~ insert point + 1까지 뒤에서부터 반복하기） {
    삽입을 위해 삽입 위치에서 i까지 데이터를 한 칸씩 뒤로 밀기
    }
    삽입 위치에 현재 데이터 삽입하기
  }
for（i: N만큼 반복하기） {
    A 배열을 통한 합 배열 S 만들기
  }
    
S 배열의 각 데이터 값을 모두 합해 결과 출력하기

 

for (int i = 1; i < n; i++) {
    int index = i;
    int value = arr[i];

    for (int j = i - 1; j >= 0; j--) {
        if (arr[i] > arr[j]) {
            // 최솟값을 선택해, 해당 위치에 삽입
            index = j + 1;
            break;
        }
        if (j == 0)
            index = 0;
    }
    for (int j = i; j > index; j--) {
        arr[j] = arr[j - 1];
    }
    arr[index] = value;
}

sum[0] = arr[0];
for (int i = 1; i < n; i++)
    sum[i] = sum[i - 1] + arr[i];
for (int x : sum)
    answer += x;

return answer;

---

(4) 퀵 정렬 : 기준값을 선정해 해당 값보다 작은 데이터와 큰 데이터를 분류하는 것을 반복해 정렬

 

N（숫자의 개수） K（K번째 수）
A（숫자 데이터 저장 배열）
for（N만큼 반복하기） {
	A 배열 저장하기
}
퀵 소트 실행하기
K번째 데이터 출력하기

[별도의 함수 구현 부분]
퀵 소트 함수（시작，종료，K）
{
    피벗 구하기 함수（시작, 종료）
    if（피벗 == K） 종료
    else if（K < 피벗） 퀵 소트 수행하기（시작, 피벗 - 1, K）
    else 퀵 소트 수행하기（피벗 + 1, 종료，K）
}

피벗 구하기 함수（시작, 종료）
{
        중앙값을 피벗으로 설정하기
        i（시작점）, j（종료점）
        while（i < j）
        {
        피벗보다 큰 수가 나올 때까지 i++
        피벗보다 작은 수가 나올 때까지 j찾은
        i와 j 데이터를 swap
        }
	피벗 데이터를 나눠진 두 그룹의 경계 index에 저장하기
}

 

	public static void sort(int[] arr, int start, int end, int k) {
		if (start < end) {
			int pivot = part(arr, start, end);
			if (pivot == k)
				return;
			else if (k < pivot)
				sort(arr, start, pivot - 1, k);
			else
				sort(arr, pivot + 1, end, k);
		}
	}

	public static int part(int[] arr, int start, int end) {
		int mid = (start + end) / 2;
		swap(arr, start, mid);
		int pivot = arr[start];
		int i = start, j = end;
		while (i < j) {
			while (pivot < arr[j]) {
				j--;
			}
			while (i < j && pivot >= arr[i]) {
				i++;
			}
			swap(arr, i, j);
		}
		arr[start] = arr[i];
		arr[i] = pivot;
		return i;
	}

	public static void swap(int[] arr, int i, int j) {
		int tmp = arr[i];
		arr[i] = arr[j];
		arr[j] = tmp;
	}

}

---

(5) 병합 정렬 

 

N（정렬할 수 개수）
A（정렬할 배열 선언하기）
tmp（정렬할 때 잠시 사용할 임시 배열 선언하기）
for（N의 개수만큼）
{
A 배열 선언하기
}
병합 정렬 함수 수행하기
결괏값 출력하기
// 병합 정렬 수행하기
병합 정렬（s, e） {
나시작점）, e（종료점）, m（중간점）
// 재귀 함수 형태로 구현하기
병합 정렬（s、m）
병합 정렬（m + 1, e）
for（s ~ e）
{
tmp 배열 저장하기
}
// 두 그룹을 병합하는 로직
indexl - 앞쪽 그룹 시작점
index2 — 뒤쪽 그룹 시작점
while（index1 <= 중간점 && index2 <= 종료점）
양쪽 그룹의 index가 가리키는 값을 비교한 후 더 작은 수를 선택해 배열에 저장하고,
선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
반복문의 끝난 후 남아 있는 데이터 정리하기
}

 

 

	private void sort(int start, int end) {
		// 최소 길이로 분할 -> 처음부터 중간점까지 집합 1, 중간점+1부터 마지막까지 집합2
		// -> 각각 정렬하는 로직
		if (end - start < 1) return;
		int mid = start + (end - start) / 2;

		sort(start, mid);
		sort(mid + 1, end);

		for (int i = start; i <= end; i++) tmp[i] = arr[i];

		// 두 그룹을 병합하는 로직
		// -> 양쪽 그룹의 index가 가리키는 값을 비교해 더 작은 수를 선택해 배열에 저장하고,
		// 선택된 데이터의 index 값을 오른쪽으로 한 칸 이동하기
		int k = start;
		int p1 = start;
		int p2 = mid + 1;

		while (p1 <= mid && p2 <= end) {
			if (tmp[p1] > tmp[p2]) {
				arr[k] = tmp[p2];
				k++;
				p2++;
			} else {
				arr[k] = tmp[p1];
				k++;
				p1++;
			}
		}

		// 한쪽 그룹이 모두 선택된 후 남아있는 값을 정리하기
		// -> 그룹끼리 재정렬 -> while문을 이용해 끝까지 반복
		while (p1 <= mid) {
			arr[k] = tmp[p1];
			k++;
			p1++;
		}
		while (p2 <= end) {
			arr[k] = tmp[p2];
			k++;
			p2++;
		}
	}
}

---

(6) 기수 정렬

 

N（정렬할 수 개수）
A（정렬할 배열 선언하기）
for（N의 개수만큼 반복하기）
{
	A 배열 저장하기
}
기수 정렬 함수 수행하기
정렬된 A 배열 출력하기


// 기수 정렬 함수 구현하기
// 변수 선언 부
bucket（현재 자릿수들의 분포를 합 배열의 형태로 알려 주는 배열）
ex: bucket[4] -> 현재 기준 자릿값이 0 ~ 4까지 몇 개의 데이터가 있는지 저장하기
output（임시 정렬을 위한 배열）
jarisu（현재 자릿수를 표현하는 수）
// 로직 부분
while（최대 자릿수만큼 반복하기）
{
    현재 기준 자릿수를 기준으로 A 배열 데이터를 bucket에 count
    합 배열 공식으로 bucket을 합 배열 형태로 변경하기
    for（N의 개수만큼 반복하기）
    {
        bucket값을 이용해 현재 기준 자릿수로 데이터를 정렬하기
        output 배열에 저장하기
    }
    for（N의 개수만큼 반복하기）
    {
    	다음 자릿수 이동을 위해 A 배열에 output 데이터 저장하기
    }
    jarisu = jarisu * 10
}

 

 

public void sort(int[] arr, int max) {
		int[] output = new int[arr.length];
		int cipher= 1;
		int cnt = 0;
		//최대 자릿수만큼 반복
		while(cnt!=max) {
			int[] bucket = new int[10];
			//0부터 9까지 이므로, 10개 -> 현재 자리 기준으로 정렬
			
			//일의 자리부터 시작
			for(int i=0;i<arr.length;i++) bucket[(arr[i]/cipher)%10]++;
			
			//합 배열을 이용해 index 계산
			for(int i=1;i<10;i++) bucket[i]+=bucket[i-1];
			
			//현재 자릿수를 기준으로 정렬
			for(int i=arr.length-1;i>=0;i--) {
				output[bucket[(arr[i]/cipher%10)]-1]=arr[i];
				bucket[(arr[i]/cipher)%10]--;
			}
			for(int i=0;i<arr.length;i++) arr[i]=output[i];
			//다음 자릿수로 이동하기 위해 현재 자릿수 기준 정렬 데이터 저장
			
			cipher=cipher*10;
			cnt++;
		}