์์ ์ฑ(stability) ํ์ธ.
#include <iostream>
#include <cassert>
#include <fstream>
using namespace std;
struct Element
{
int key;
char value;
};
void Print(Element* arr, int size)
{
for (int i = 0; i < size; i++)
cout << arr[i].key << " ";
cout << endl;
for (int i = 0; i < size; i++)
cout << arr[i].value << " ";
cout << endl;
}
int main()
{
// ์์ ์ฑ ํ์ธ(unstable)
{
Element arr[] = { {2, 'a'}, {2, 'b'}, {1, 'c' } };
int size = sizeof(arr) / sizeof(arr[0]);
Print(arr, size);
int min_index;
for(int i = 0; i < (size - 1); i++)
{
min_index = i;
for (int j = (i + 1); j < size; j++)
{
if (arr[j].key < arr[min_index].key)
{
min_index = j;
}
}
swap(arr[i], arr[min_index]);
Print(arr, size);
}
}
return 0;
}
์คํ ๊ฒฐ๊ณผ
2 2 1
a b c
1 2 2
c b a
1 2 2
c b a
์ ๋ ฌ์ ์์ ์ฑ(stablity)์ด๋ผ๋ ๊ฐ๋ ์ด ์์ต๋๋ค.
- ์ด ๊ฐ๋
์
stable
ํ์งunstable
ํ์ง๋ก ๊ตฌ๋ถํฉ๋๋ค.- ์ฆ, ์์ ์ ์ธ์ง ๋ถ์์ ์ ์ธ์ง๋ก ๊ตฌ๋ถํฉ๋๋ค.
์ ์ฝ๋์์ ๋ณด๋ฉด Element
๋ฐฐ์ด์ ์ ๋ ฌํฉ๋๋ค.
์ด รlement
๋ฅผ ๋ณด๋ฉด ๋ค์๊ณผ ๊ฐ์ต๋๋ค.
struct Element
{
int key;
char value;
};
-
Element
์key
๋ ์ ์์ด๊ณvalue
๋ ๋ฌธ์์ ๋๋ค.- ๊ทธ๋์ ์ ๋ ฌํ ๋
key
๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํฉ๋๋ค.- ๊ทธ๋ฌ๋ฉด
swap
์value(๋ฌธ์)
๋ ํจ๊ป ๋ฐ๋ผ๊ฐ๋๋ค. -> ๋ณต์ฌ๋ฅผ ํ๋ ๋ฐ๋ผ๊ฐ๋ ๊ฒ ์ ๋๋ค.
- ๊ทธ๋ฌ๋ฉด
- ๊ทธ๋์ ์ ๋ ฌํ ๋
Element arr[] = { {2, 'a'}, {2, 'b'}, {1, 'c' } };
- ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค์ ์์์
key
๋2
์ด๊ณvalue
๋'a'
์ ๋๋ค. - ๋ ๋ฒ์งธ ์ธ๋ฑ์ค์ ์์์
key
๋2
์ด๊ณvalue
๋'b'
์ ๋๋ค. - ์ธ ๋ฒ์งธ ์ธ๋ฑ์ค์ ์์์
key
๋1
์ด๊ณvalue
๋'c'
์ ๋๋ค.
โ์ ๋ ฌ์์๋ key
๊ฐ ์์ ์์๋๋ก ์ ๋ ฌ๋๋๋ก ํ ๊ฒ ์
๋๋ค.โ
- ์ฆ,
key
๋ฅผ ๊ธฐ์ค์ผ๋ก ์ ๋ ฌํฉ๋๋ค.
์ฌ๊ธฐ์ ์ฃผ๋ชฉํด์ผ ํ ์ ์ โ์ฒซ ๋ฒ์งธ ์ธ๋ฑ์ค์ ๋ ๋ฒ์งธ ์ธ๋ฑ์ค์ ์์์ Valueโ์ ๋๋ค.
- ๋ ์ธ๋ฑ์ค์ ์์์
key
๊ฐ์ ๊ฐ์ผ๋value
๊ฐ์ ๋ค๋ฆ ๋๋ค.
๋น๊ต ๋ก์ง์ ๋ณด๋ฉด key
๊ฐ์ ๊ฐ์ง๊ณ ๋น๊ต๋ฅผ ํ์ง๋ง swap
์์๋ key
์ value
๋ฅผ ๋ชจ๋ ๊ฐ์ง๊ณ ์์ง์
๋๋ค.
์คํ ๊ฒฐ๊ณผ๋ฅผ ๋ณด๊ณ value์ ์์ ์ฑ์ ์๊ด ๊ด๊ณ์ ๋ํด ์์๋ด ์๋ค.
์คํ ๊ฒฐ๊ณผ
2 2 1
a b c
1 2 2
c b a
1 2 2
c b a
- ์คํ ๊ฒฐ๊ณผ๋ฅผ ๋ณด๋ฉด (2 a), (2, b), (1, c)์์ โ(1, c), (2, b), (2, a)โ ์์ผ๋ก ์ ๋ ฌ๋ ๊ฒ์ ๋ณผ ์ ์์ต๋๋ค.
- ์ฒ์์๋ (2 a), (2, b) ์์์์ง๋ง ์ ๋ ฌ ํ์๋ โ(2, b), (2, a)โ ๋ก ์์๊ฐ ๋ฐ๋์ด ์ ๋ ฌ๋์์ต๋๋ค.
- value๊ฐ ๋ค๋ฐ๋ ๊ฒ์ ์ ์ ์์ต๋๋ค.
- key๊ฐ ์ ๋ ฌ์ด ๋์์ผ๋ฏ๋ก ์ ๋ ฌ์ ์ ๋์๋ค๊ณ ๋ณผ ์ ์์ต๋๋ค.
-
๊ทธ๋ฌ๋ โkey๊ฐ ๊ฐ์ ๊ฐ์ผ ๊ฒฝ์ฐ์๋ value์ ์์๊ฐ a, b์์ b, a ๋ก ๋ฐ๋์์ต๋๋ค.โ
- โ์ฌ๊ธฐ์ stableํ ๊ฒ๊ณผ unstableํ ๊ฒ์ ์ฐจ์ด์ ์ด ๋ํ๋ฉ๋๋ค.โ
- value๊ฐ ๋ค๋ฐ๋ ๊ฒ์ ์ ์ ์์ต๋๋ค.
- ์ฒ์์๋ (2 a), (2, b) ์์์์ง๋ง ์ ๋ ฌ ํ์๋ โ(2, b), (2, a)โ ๋ก ์์๊ฐ ๋ฐ๋์ด ์ ๋ ฌ๋์์ต๋๋ค.
โํค ๊ฐ์ด ๊ฐ์๋ ์ ๋ ฌ์ ๋ฒจ๋ฅ ๊ฐ์ด ์ฒ์๊ณผ ๊ฐ์ด ์ ์ง๊ฐ ๋๋ค๋ฉด ๊ทธ๊ฒ์ stableํ๋ค๋ผ๊ณ ํฉ๋๋ค, ๊ทธ์ ๋ฐ๋๋ก ํค ๊ฐ์ด ๊ฐ์ผ๋ ์ฒ์๊ณผ ๋ฌ๋ฆฌ ๋ฒจ๋ฅ์ ์์๊ฐ ๋ฐ๋ ๊ฒฝ์ฐ์๋ unstableํ๋ค ๋ผ๊ณ ํฉ๋๋ค.โ
- ์ด๊ฒ๋ ์ ๋ ฌ ์๊ณ ๋ฆฌ์ฆ์ ๋ถ๋ฅํ๋ ๊ธฐ์ค ์ค ํ๋์ ๋๋ค.