counting sort - kurkim0661/jihwan GitHub Wiki
μΉ΄μ΄ν μ λ ¬μ μκ° λ³΅μ‘λλ O(n) ν μ λ ¬λ³΄λ€ λΉ λ₯΄μ§λ§ λ¨μ μ΄ μλ€... μΉ΄μ΄ν λ°°μ΄μ λ§λ€μ΄μΌνλλ° μ΄μ λ°λΌμ λ©λͺ¨λ¦¬ μ©λμ΄ κ²½μ°μ λ°λΌμ κ΅μ₯ν 컀μ§λ μν©μ΄ λ²μ΄μ§ μ μλ€. μν©μ λ°λΌμ ν΄μΌν λ―... μΉ΄μ΄ν μνΈκ° μλλ€λ©΄ ν΅μνΈκ° μ’μ λμμ΄ λ κ²!
void countSort(vector & arr)
{
int max = *max_element(arr.begin(), arr.end());
int min = *min_element(arr.begin(), arr.end());
int range = max - min + 1;
vector<int> count(range), output(arr.size());
for(int i = 0; i < arr.size(); i++)
count[arr[i]-min]++;
for(int i = 1; i < count.size(); i++)
count[i] += count[i-1];
for(int i = arr.size()-1; i >= 0; i--)
{
output[ count[arr[i]-min] -1 ] = arr[i];
count[arr[i]-min]--;
}
for(int i=0; i < arr.size(); i++)
arr[i] = output[i];
}
void printArray(vector & arr)
{
for (int i=0; i < arr.size(); i++)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10};
countSort (arr);
printArray (arr);
return 0;
}