
์์๋๋ฉด ์ ์ฉํ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์๊ฐ ๋ณต์ก๋ ๋ถ์
์์๋๋ฉด ์ ์ฉํ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๊ณผ ์๊ฐ ๋ณต์ก๋ ๋ถ์ ๊ด๋ จ
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ์ดํฐ๋ฒ ์ด์ค ์์คํ , ๊ฒ์ ์์ง, ๋จธ์ ๋ฌ๋ ์๊ณ ๋ฆฌ์ฆ, ์ผ์์ํ์ ๋ค์ํ ๋์งํธ ์๋น์ค์์ ํ์ฉ๋ฉ๋๋ค. ์๊ณ ๋ฆฌ์ฆ์ ํจ์จ์ฑ์ ๋ณดํต **์๊ฐ ๋ณต์ก๋(Time Complexity)**๋ก ๋ํ๋ด๋ฉฐ, ํ๋ก๊ทธ๋จ ์ฑ๋ฅ์ ํฐ ์ํฅ์ ๋ฏธ์น ์ ์์ผ๋ฏ๋ก ์ต์ ํํ๋ ๊ฒ์ด ์ค์ํฉ๋๋ค.
์ด๋ฒ ๊ธ์์๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ข ๋ฅ ์ค ์ฝ์ ์ ๋ ฌ, ๋ณํฉ ์ ๋ ฌ, ํต ์ ๋ ฌ์ ๋ํด ์ดํด๋ณด๊ณ , ๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋น๊ตํ์ฌ ์ด๋ค ๊ฒฝ์ฐ์ ์ฌ์ฉํด์ผ ํ๋์ง ์์๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค.
์ฝ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ(Insert Sort)
1) ๋์ ์๋ฆฌ
์ฝ์ ์ ๋ ฌ(Insertion Sort) ์๊ณ ๋ฆฌ์ฆ์ ๋ฐฐ์ด์ ๊ฐ ์์๋ฅผ ์ ์ ํ ์์น์ ์ฝ์ ํ๋ ๋ฐฉ์์ผ๋ก ๋์ํฉ๋๋ค. ์ด๊ธฐ์๋ ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ์์๋ฅผ ์ด๋ฏธ ์ ๋ ฌ๋ ๊ฒ์ผ๋ก ๊ฐ์ฃผํ๊ณ , 2๋ฒ์งธ ์์๋ถํฐ ์์ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ฐ๋ณต๋ฌธ์ผ๋ก ํด๋น ์์์ ๊ฐ์ฅ ๊ฐ๊น์ด ์ข์ธก ์์๋ถํฐ ๋น๊ตํ๋ฉด์ ์ฝ์ ์์น๋ฅผ ํ์ธํฉ๋๋ค.

์๋ฅผ ๋ค์ด, ์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด [3, 2, 1, 4, 5]์ด๋ผ๋ ๋ฐฐ์ด์ด ์๋ ๊ฒฝ์ฐ, ์ฒซ ๋ฒ์งธ ๋จ๊ณ์์๋ 2๋ฒ์งธ ์์์ธ [2]
๋ฅผ ๋จผ์ ์ ํํฉ๋๋ค. ๋ค์์ผ๋ก [2]
๋ฅผ ์ข์ธก์ ์๋ ์์์ ํ๋์ฉ ๋น๊ตํฉ๋๋ค. ์ฌ๊ธฐ์๋ [3] > [2]
์ด๊ธฐ ๋๋ฌธ์ ๋ ์์น๋ฅผ ๋ฐ๊ฟ์ค๋๋ค. [2]
์ ์ข์ธก์๋ ๋์ด์ ์ซ์๊ฐ ์๊ธฐ ๋๋ฌธ์ ๋น๊ต๋ฅผ ์ข
๋ฃํฉ๋๋ค.

๋ค์์๋ 3๋ฒ์งธ ์์์ธ [1]
์ ์ ํํ์ฌ ์ข์ธก์ ์๋ ์ซ์๋ค๊ณผ ๋น๊ตํฉ๋๋ค. ๋จผ์ [3]
๊ณผ ๋น๊ตํด์ ์๋ฆฌ๋ฅผ ๋ฐ๊พธ๊ณ ๋ค์์ผ๋ก [2]
๋น๊ตํด์ ์๋ฆฌ๋ฅผ ๋ฐ๊ฟ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ค์ 4๋ฒ์งธ ์์์ธ [4]
๋ก ์ด๋ํฉ๋๋ค. [4]
๋ถํฐ๋ ์ข์ธก์ ์๋ ์ซ์ ์ค ํฐ ์ซ์๊ฐ ์๊ธฐ ๋๋ฌธ์ ๊ทธ ์๋ฆฌ๋ฅผ ๊ทธ๋๋ก ์ ์งํฉ๋๋ค. ์ฝ์
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์ด๋ฌํ ๋ฐฉ์์ผ๋ก ์ซ์ ๋ฐฐ์ด์ ์ ๋ ฌํฉ๋๋ค.
2) ์ฝ๋ ์์
๋ค์์ ์ฝ์
์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ ์๋ฐ ์ฝ๋ ์์์
๋๋ค. for๋ฌธ์์๋ i=1
๋ก ์ค์ ํ์ฌ ๋ฐฐ์ด์ย 2๋ฒ์งธ ์์๋ถํฐ ์์ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ while๋ฌธ์ผ๋ก ์ข์ธก์ ์๋ ์ซ์์ ๋น๊ตํ์ฌ ํฐ ์ซ์๊ฐ ์๋ ๊ฒฝ์ฐ ์์น๋ฅผ ๋ฐ๊ฟ๋๋ค.

์ด์ ํด๋ผ์ด์ธํธ ์ฝ๋์์ insertSort()
๋ฉ์๋๋ฅผ ํธ์ถํ์ฌ ์์์ ์ซ์ ๋ฐฐ์ด์ ์ ๋ ฌํด ๋ณด๋๋ก ํ๊ฒ ์ต๋๋ค. ์ฝ๋๋ฅผ ์คํํ๋ฉด ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๋ฐฐ์ด์ด ์ ๋ ฌ๋๋ ๊ฒ์ ํ์ธํด ๋ณผ ์ ์์ต๋๋ค.

๋ณํฉ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ(Merge Sort)
1) ๋์ ์๋ฆฌ
๋ณํฉ ์ ๋ ฌ(Merge Sort)์ ๋ํ์ ์ธ ๋ถํ ์ ๋ณต(Divide and Conquer) ์๊ณ ๋ฆฌ์ฆ ์ค ํ๋์ ๋๋ค. ๋ณํฉ ์ ๋ ฌ์์๋ ๋จผ์ ๋ฐฐ์ด์ ๋ ๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด๋ก ๋ถํ ํ๊ณ , ๊ฐ ๋ถ๋ถ ๋ฐฐ์ด์ ์ ๋ ฌํ๋ ๋ถํ ์ ๋ณต ๋จ๊ณ๋ฅผ ๊ฑฐ์นฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๋ ๊ฐ์ ์ ๋ ฌ๋ ๋ถ๋ถ ๋ฐฐ์ด์ ๋ณํฉํ์ฌ ์ต์ข ์ ์ผ๋ก ํ๋์ ์ ๋ ฌ๋ ๋ฐฐ์ด์ ๋ง๋๋ ๋ฐฉ์์ผ๋ก ๋์ํฉ๋๋ค.
๋ถํ (Divide)
์ฃผ์ด์ง ๋ฐฐ์ด์ ๋ ๊ฐ์ ๋์ผํ ํฌ๊ธฐ์ ๋ถ๋ถ ๋ฐฐ์ด๋ก ๋ถํ ํฉ๋๋ค. ๋ง์ฝ ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ ํ์๋ผ๋ฉด, ๋ถ๋ถ ๋ฐฐ์ด์ ๋ค๋ฅธ ๋ถ๋ถ ๋ฐฐ์ด๋ณด๋ค ์์๊ฐ ํ๋ ๋ ๋ง์ ์ ์์ต๋๋ค.
์ ๋ณต(Conquer)
์ ๋ณต ๋จ๊ณ์์๋ ๋ ๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด์ ์ ๋ ฌํฉ๋๋ค. ๋ง์ฝ ๋ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ๋ค์ ๋๋ ์ ์๋ค๋ฉด, ๋ค์ ๋ถํ ๋จ๊ณ๋ก ์ฌ๊ท์ ํธ์ถ(recursive call)์ ์งํํฉ๋๋ค.
๋ณํฉ(Merge)
๋ ๊ฐ์ ์ ๋ ฌ๋ ๋ถ๋ถ ๋ฐฐ์ด์ ๋ณํฉํ์ฌ ํ๋์ ์ ๋ ฌ๋ ๋ฐฐ์ด๋ก ๋ง๋ญ๋๋ค. ์ด ๊ณผ์ ์ ๋ ๋ถ๋ถ ๋ฐฐ์ด์ ์ฒซ ๋ฒ์งธ ์์๋ถํฐ ๋น๊ตํ์ฌ ์์ ์ซ์๋ฅผ ๋ณํฉ๋ ๋ฐฐ์ด์ ์ฐจ๋ก๋๋ก ๋ฃ๋ ๋ฐฉ์์ผ๋ก ์งํ๋ฉ๋๋ค. ๊ฒฐ๊ณผ์ ์ผ๋ก ๋ ๋ถ๋ถ ๋ฐฐ์ด์ ๋ชจ๋ ์์๊ฐ ๋ณํฉ๋ ๋ฐฐ์ด๋ก ์ด๋ํ ๋๊น์ง ๋ณํฉ ๋จ๊ณ๋ฅผ ๋ฐ๋ณตํฉ๋๋ค.

2) ์ฝ๋ ์์
๋ค์ ์ฝ๋๋ ๋ณํฉ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๊ตฌํํ ์๋ฐ ์ฝ๋์
๋๋ค. mergeSort()
๋ฉ์๋์์ ๋จผ์ ๋ฐฐ์ด์ ํฌ๊ธฐ๋ฅผ ์ฒดํฌํ์ฌ, ๊ฐ์ฅ ์์ ๋จ์์ ๋ฐฐ์ด ํฌ๊ธฐ๊ฐ ๋๋ฉด ์ฌ๊ท ํธ์ถ์์ ๋น ์ ธ๋์ค๋๋ก ์กฐ๊ฑด(Base Case)์ ์ค์ ํฉ๋๋ค. ๊ทธ๋ฆฌ๊ณ ๊ธฐ์กด ๋ฐฐ์ด์ 2๊ฐ๋ก ๋ถํ ํ๊ณ , ๊ฐ ๋ฐฐ์ด์ ๋ํ mergeSort()
์ฌ๊ท ํธ์ถ๊ณผ ๋ณํฉ ๋ฉ์๋์ธ merge()
๋ฅผ ํธ์ถํ๋๋ก ํฉ๋๋ค.
/** Merge Sort **/
public void mergeSort(int[] inputArray) {
int inputLength = inputArray.length;
if (inputLength < 2) { // ๋ฐฐ์ด ํฌ๊ธฐ๊ฐ 2๋ณด๋ค ์์ผ๋ฉด ๋ถํ ์ข
๋ฃ
return;
}
int midIndex = inputLengtn / 2; // ๋ฐฐ์ด์ 2๊ฐ๋ก ๋๋๊ธฐ
int[] leftHalf = new int[midIndex];
int[] rightHalf = new int[inputLength - midIndex];
for (int i= 0; 1<midIndex; 1++) {// ์ข์ธก ๋ฐฐ์ด ์์ฑ
leftHalf [i] = inputArray [i];
}
for (int 1= midIndex; 1< inputLengtn; 1++) {// ์ฐ์ธก ๋ฐฐ์ด ์์ฑ
rightHalf[i - midIndex] = inputArray (i];
}
mergeSort(LeftHalf) ; // ์ข์ธก ๋ฐฐ์ด์ ์ฌ๊ท ํธ์ถ๋ก ๋ถํ
mergeSort(rightHalf) ; // ์ฐ์ธก ๋ฐฐ์ด์ ์ฌ๊ท ํธ์ถ๋ก ๋ถํ
merge(inputArray, leftHalf, nightHalf); // ๋ถํ ๋ ๋ฐฐ์ด์ ๋ณํฉ
}
merge()
๋ฉ์๋์์๋ ๋ ๋ฐฐ์ด์ ์ข์ธก ์ซ์๋ถํฐ ๋น๊ตํ์ฌ ์์ ์ซ์๋ฅผ ์ฐจ๋ก๋๋ก ๋ณํฉ๋ ๋ฐฐ์ด์ ๋ฃ์ต๋๋ค. ๋ง์ฝ ํ ์ชฝ ๋ฐฐ์ด์ ์ซ์๊ฐ ๋จ์ ์์ผ๋ฉด while loop๋ก ๋ณํฉ๋ ๋ฐฐ์ด์ ๋จ์ ์ซ์๋ค์ ์ฑ์์ค๋๋ค.
private void merge(int[] inputArray, int[] leftHalf, int[] rightHalf) {
int leftLength = leftHalf.length;
int rightLength = rightHalf.length;
int 1 = 0, 1 = 0, k = 0;
// ์ข์ธก ๋ฐฐ์ด๊ณผ ์ฐ์ธก ๋ฐฐ์ด์ ๋น๊ตํ์ฌ ๋ณํฉ
while (i < leftLength && j < rightLength) {
if (leftHalf[i] <= rightHalf[i]) {
inputArray[k] = leftHalf[i];
i++;
} else {
inputArray [k] = rightHalfli];
j++;
}
k++;
}
while(i < LeftLength) { // ์ข์ธก ๋ฐฐ์ด์ ๋จ์ ์์๊ฐ ์๋ ๊ฒฝ์ฐ
inputArray[k] = leftHalf[i];
i++;
k++;
}
while(1 < nightLength) { // ์ฐ์ธก ๋ฐฐ์ด์ ๋จ์ ์์๊ฐ ์๋ ๊ฒฝ์ฐ
inputArray[k] = rightHalf[j];
j++;
k++;
}
}
์ด์ ์์ ์ฝ์ ์ ๋ ฌ๊ณผ ๋ง์ฐฌ๊ฐ์ง๋ก ํด๋ผ์ด์ธํธ ์ฝ๋์์ ๋ณํฉ ์ ๋ ฌ ๋ฉ์๋๋ฅผ ํธ์ถํ์ฌ ๊ฒฐ๊ณผ๋ฅผ ํ์ธํด ๋ณด๋ฉด, ๋ค์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ๋ฐฐ์ด์ด ์ ์ ๋ ฌ๋๋ ๊ฒ์ ๋ณผ ์ ์์ต๋๋ค.
public class Client {
public static void main(String(] args) {
Random rand = new Random;
int[] inputArray = new int [10];
for (int i = 0; i โน inputArray.length; i++) {
inputArray [i] = rand.nextInt( bound: 100);
}
System.out.println("Before sorted: ");
System.out.println(Arrays.toString(inputArray));
Sorting sorting = new Sorting;
// ๋ณํฉ ์ ๋ ฌ ํธ์ถ
sorting-mergeSort(inputArray);
System.out.println("After sorted: ");
System.out.println(Arrays.toString(inputArray));
}
}
//
// Before sorted:
// [62, 5, 40, 46, 26, 11, 53, 8, 71, 41
// After sorted:
// [4, 5, 8, 11, 26, 40, 46, 53, 62, 71]
ํต ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ(Quick Sort)
1) ๋์ ์๋ฆฌ
ํต ์ ๋ ฌ(Quick Sort)๋ ๋ถํ ์ ๋ณต ์ ๋ต์ ์ฌ์ฉํ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ํต ์ ๋ ฌ์ ๋ฐฐ์ด์์ **ํผ๋ฒ(Pivot)**์ ์ ํํ๊ณ , ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก **ํํฐ์ (Partition)**์ ๋๋์ด ๋ฐฐ์ด์ ์ ๋ ฌํ๋ ๋ฐฉ์์ผ๋ก ์งํ๋ฉ๋๋ค. ๋ณํฉ ์ ๋ ฌ๊ณผ ๋ค๋ฅธ ์ ์ ํต ์ ๋ ฌ์์๋ ๋ณํฉ ๊ณผ์ ์ด ํ์ํ์ง ์๋ค๋ ๊ฒ์ ๋๋ค. ๋ถํ ๊ณผ์ ์์ ํผ๋ฒ์ผ๋ก ์ ํ๋ ์์๋ค์ด ๋ฐฐ์ด ๋ด์์ ์์ ์ ์ต์ข ์์น์ ๋ฐฐ์น๋๊ธฐ ๋๋ฌธ์ ๋๋ค.
ํผ๋ฒ ์ ํ(Pivot Selection)
๋ฐฐ์ด์์ ์์ ํ๋๋ฅผ ํผ๋ฒ์ผ๋ก ์ ํํฉ๋๋ค. ํผ๋ฒ ์ ํ ๋ฐฉ๋ฒ์ ์ฌ๋ฌ ๊ฐ์ง๊ฐ ์์ผ๋ฉฐ, ์ด์ ๋ฐ๋ผ ์๊ณ ๋ฆฌ์ฆ์ ์ฑ๋ฅ์ด ๋ฌ๋ผ์ง๊ธฐ๋ ํฉ๋๋ค.
๋ถํ (Partition)
์ ํํ ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก ๋ฐฐ์ด์ ๋ ๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด๋ก ๋ถํ ํฉ๋๋ค. ํผ๋ฒ๋ณด๋ค ์๊ฑฐ๋ ๊ฐ์ ์์๋ค์ ์ข์ธก ๋ถ๋ถ ๋ฐฐ์ด์, ํผ๋ฒ๋ณด๋ค ํฐ ์์๋ค์ ์ฐ์ธก ๋ถ๋ถ ๋ฐฐ์ด์ ์์นํ๊ฒ ๋ฉ๋๋ค.
์ ๋ณต(Conquer)
๋ ๊ฐ์ ๋ถ๋ถ ๋ฐฐ์ด์ ์ฌ๊ท์ ์ผ๋ก ํธ์ถํ๋ฉฐ, ๋ถ๋ถ ๋ฐฐ์ด์ ํฌ๊ธฐ๊ฐ 0 ๋๋ 1์ด ๋ ๋๊น์ง ๋ฐ๋ณตํฉ๋๋ค.

์๋ฅผ ๋ค์ด, ์ ๊ทธ๋ฆผ์ฒ๋ผ [2, 5, 1, 4, 3]
๋ฐฐ์ด์ ํต ์ ๋ ฌ๋ก ์ ๋ ฌํ๋ ๊ฒฝ์ฐ ์ฐ์ ๋ฐฐ์ด์ ๊ฐ์ฅ ๋ง์ง๋ง ์์์ธ [3]
์ ํผ๋ฒ์ผ๋ก ์ ํํฉ๋๋ค. ๊ทธ๋ค์ ํผ๋ฒ [3]
์ ๊ธฐ์ค์ผ๋ก [2, 1]
๊ณผ [4, 5]
๋ ๊ฐ์ ํํฐ์
์ผ๋ก ๋ถํ ํฉ๋๋ค. ๊ฐ ํํฐ์
์ ๋ํด ์ฌ๊ท ํธ์ถ์ ํ์ฌ ์์ ๊ณผ์ ์ ๋ฐ๋ณตํ๋ฉด์ ์ ์ฒด ๋ฐฐ์ด์ ์ ๋ ฌํฉ๋๋ค.
2) ์ฝ๋ ์์
๋ค์์ ํต ์ ๋ ฌ์ ๊ตฌํํ ์๋ฐ ์ฝ๋ ์์์
๋๋ค. quickSort()
๋ฉ์๋์์๋ ์ ๋ ฌ ์ํฌ ๋ฐฐ์ด๊ณผ ๋ฐฐ์ด์ ์ต์ ์ต๋ ์ธ๋ฑ์ค(low, high index)๋ฅผ ์ธ์(Parameter)๋ก ๊ฐ์ด ๋๊ฒจ์ค๋๋ค. quickSort()
๋ฉ์๋์์๋ ๋ค์ ํผ๋ฒ์ ๋ฆฌํดํ๋ partition()
๋ฅผ ํธ์ถํ๊ณ , ๋ฆฌํด ๋ฐ์ ํผ๋ฒ์ ๊ธฐ์ค์ผ๋ก ๋ถํ ๋ ์ข์ธก, ์ฐ์ธก ๋ฐฐ์ด์ ์ฌ๊ท ํธ์ถํฉ๋๋ค.

partition()
๋ฉ์๋์์๋ ๋ฐฐ์ด์ ๋ง์ง๋ง ์์๋ฅผ ํผ๋ฒ์ผ๋ก ์ค์ ํ๊ณ , ๋ฐ๋ณต๋ฌธ์ผ๋ก ํผ๋ฒ๋ณด๋ค ์์ ์์๋ ์ข์ธก ๋ถ๋ถ ๋ฐฐ์ด์ ๋ฐฐ์นํ๊ณ , ํฐ ์์๋ ์ฐ์ธก ๋ถ๋ถ ๋ฐฐ์ด์ ๋ฐฐ์นํฉ๋๋ค. ๋ฐ๋ณต๋ฌธ์ด ๋๋๋ฉด ํด๋น ํผ๋ฒ์ ์ข์ธก ๋ฐฐ์ด์ ๋ง์ง๋ง, ์ฆ ์ข์ธก ๋ฐฐ์ด๊ณผ ์ฐ์ธก ๋ฐฐ์ด์ ์ฌ์ด์ ์์น ์์ผ ์ต์ข
์ ์ธ ์์น๋ฅผ ํ์ ํฉ๋๋ค.

์ด์ ํด๋ผ์ด์ธํธ ์ฝ๋์์ ์์ ๊ตฌํํ ํต ์ ๋ ฌ์ ์คํํฉ๋๋ค. ๊ทธ๋ฌ๋ฉด ๋ค์ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ํต ์ ๋ ฌ๋ ์ ์์ ์ผ๋ก ๋์ํ๋ ๊ฒ์ ์ดํด๋ณผ ์ ์์ต๋๋ค.

๊ฐ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ์๊ฐ ๋ณต์ก๋ ๋น๊ต ๋ถ์
1) ์๊ฐ ๋ณต์ก๋ ๋ถ์
์๊ฐ ๋ณต์ก๋๋ ์๊ณ ๋ฆฌ์ฆ์ ํจ์จ์ฑ์ ์ธก์ ํ๋ ์งํ์ด๋ฉฐ, ์ด๋ค ๋ฌธ์ ๋ฅผ ํด๊ฒฐํ๋ ๋ฐ ์ด๋ ์ ๋ ์๊ฐ์ด ๊ฑธ๋ฆฌ๋์ง๋ฅผ ๋ํ๋ ๋๋ค. ์ผ๋ฐ์ ์ผ๋ก ๋น ์ค(Big O) ํ๊ธฐ๋ฒ์ผ๋ก ์๊ฐ ๋ณต์ก๋๋ฅผ ํํํ๋ฉฐ, ์ ๋ ฅ ํฌ๊ธฐ์ ๋ํ ํจ์๋ก ๋ํ๋ ๋๋ค.
F\left(right) = O\left(G\left(n\right)\right)
์ฌ๊ธฐ์ ์ํ์ ์ผ๋ก ๊น๊ฒ ๋ค์ด๊ฐ๋ฉด ์กฐ๊ธ ๋ณต์กํด์ง์ง๋ง, ๊ฐ๋จํ๊ฒ ํํํ์๋ฉด ์ด 1์ฐจ ๋คํญ์์ด๋ฉด ์ผ๋ก ํ๊ธฐํ๊ณ , 2์ฐจ ๋คํญ์์ด๋ฉด ์ผ๋ก ํ๊ธฐํฉ๋๋ค. ์๊ฐ ๋ณต์ก๋๋ ์๋ ๊ทธ๋ฆผ๊ณผ ๊ฐ์ด ์ด ๊ฐ์ฅ ํจ์จ์ ์ด๋ฉฐ, ๋ค์์ผ๋ก , ๋ฑ์ด ๋ฐ๋ฆ ๋๋ค. ์ดํ๋ถํฐ๋ ์ ๋ ฅ ํฌ๊ธฐ๊ฐ ์ปค์ง์๋ก ์ฒ๋ฆฌ ์๊ฐ์ด ๊ธ๊ฒฉํ ๋๊ธฐ ๋๋ฌธ์ ๋นํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ผ๋ก ์ฌ๊ฒจ์ง๋๋ค.

randerson112358
)2) ๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋ ๋น๊ต
์๊ณ ๋ฆฌ์ฆ ์๊ฐ ๋ณต์ก๋๋ ์ต์ (Best case), ์ต์ (Worst case), ํ๊ท (Average case)์ผ๋ก ๋๋ ์ ๋ถ์ํ ์ ์์ต๋๋ค. ์ฝ์ ์ ๋ ฌ, ๋ณํฉ ์ ๋ ฌ, ํต ์ ๋ ฌ์ ๋ํ ์ต์ , ์ต์ , ํ๊ท ์๊ฐ ๋ณต์ก๋๋ ๋ค์ ํ์ ๊ฐ์ต๋๋ค.

3) ์ฅ๋จ์ ๋ฐ ์ฌ์ฉ ๋ฐฉ๋ฒ
์ฝ์ ์ ๋ ฌ์ ๊ตฌํ์ด ๊ฐ๋จํ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ํ์ง๋ง, ํ๊ท ์ ์ผ๋ก O(n2)์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๊ฐ์ง๊ธฐ ๋๋ฌธ์ ์ผ๋ฐ์ ์ผ๋ก ๋นํจ์จ์ ์ธ ์๊ณ ๋ฆฌ์ฆ์ด๋ผ๊ณ ํ ์ ์์ต๋๋ค. ๋ฐ๋ผ์ ์ฝ์ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋ฐ์ดํฐ์ ์ด ๊ทนํ ์ ํ์ ์ธ ๊ฒฝ์ฐ ์ธ์๋ ์ ์ฌ์ฉํ์ง ์์ต๋๋ค.
๋ณํฉ ์ ๋ ฌ์ ์ต์ ์ ๊ฒฝ์ฐ์๋ ์ด๋ ์ ๋ ์ฑ๋ฅ์ ๋ณด์ฅํ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋๋ค. ๋ค๋ง ๋ถ๋ถ ๋ฐฐ์ด์ ์ ์ฅํ ์ถ๊ฐ์ ์ธ ๋ฉ๋ชจ๋ฆฌ๊ฐ ํ์ํ๋ฏ๋ก, ๋ฐ์ดํฐ์ ์ด ์ปค์ง์๋ก ๊ณต๊ฐ ๋ณต์ก๋์ ๋ํ ๊ณ ๋ ค๊ฐ ํ์ํฉ๋๋ค. ๋ณํฉ ์ ๋ ฌ์ ํน๋ณํ ๊ณต๊ฐ์ ์ธ ๋ถ๋ถ์ ๋ฌธ์ ๊ฐ ์๋ค๋ฉด, ์ต์ ์ ๊ฒฝ์ฐ์๋ ์ข์ ์ฑ๋ฅ์ ๋ณด์ด๊ธฐ ์ํด ์ฌ์ฉํ ์ ์์ต๋๋ค.
ํต ์ ๋ ฌ์ ๋ณํฉ ์ ๋ ฌ๊ณผ ๋ฌ๋ฆฌ ์ถ๊ฐ ๋ฉ๋ชจ๋ฆฌ๊ฐ ๊ฑฐ์ ํ์ํ์ง ์์ต๋๋ค. ๋ค๋ง ์ต์ ์ ๊ฒฝ์ฐ ์ฑ๋ฅ์ด ๋จ์ด์ง ์ ์๋ค๋ ๋จ์ ์ด ์์ต๋๋ค. ๋ฐ๋ผ์ ๋ฉ๋ชจ๋ฆฌ๊ฐ ์ ํ์ ์ธ ํ๊ฒฝ์์ ๋ฐ์ดํฐ์ ์ด ๋๋ฌด ํฌ์ง ์์ ๋ ์ฌ์ฉํ๋ ๊ฒ์ด ์ข์ต๋๋ค.
๋ง์น๋ฉฐ
์ง๊ธ๊น์ง ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ์ค ์ฝ์ ์ ๋ ฌ, ๋ณํฉ ์ ๋ ฌ, ํต ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋ํด์ ์์๋ณด๊ณ , ๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋๋ฅผ ๋น๊ตํด ๋ณด์์ต๋๋ค. ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋์ ๋ํด ์๊ณ ์์ผ๋ฉด ํน์ ์กฐ๊ฑด ํ์ ๊ฐ์ฅ ์ ํฉํ ์๊ณ ๋ฆฌ์ฆ์ ์ ํํ ์ ์์ผ๋, ๊ฐ ์๊ณ ๋ฆฌ์ฆ์ ์๊ฐ ๋ณต์ก๋ ํ๋ ์ด๋ ์ ๋ ์๊ธฐํด ๋๋ ๊ฒ์ด ์ข์ต๋๋ค. ์ถ๊ฐ๋ก, ์์์ ์ดํด๋ณธ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ ์ธ์๋ ํ ์ ๋ ฌ, ๋ธ๋ก ๋ณํฉ ์ ๋ ฌ,ย ์ธํธ๋ก ์ ๋ ฌ ๊ฐ์ ๋ค์ํ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ๋ ์์ผ๋ ์ฐธ๊ณ ํ๊ธธ ๋ฐ๋๋๋ค.