FazBrowse GitHub Viewer | Trending | | Home

Tools: [Download Repo ZIP] [View Raw Code] [Original HTTPS Page]

basic-programs/Sorting/CountingSort.cpp at master · starVader/basic-programs · GitHub

42 lines (35 loc) · 983 Bytes

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

// Counting sort with C++

#include <algorithm>

#include <iostream>

#include <vector>

using namespace std;

void countSort(vector<int>& 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<int>& arr)

{

for (int i = 0; i < arr.size(); i++)

cout << arr[i] << " ";

cout << "\n";

}

int main()

{

vector<int> arr = { -6, -2, 5, 5, -1, 11 };

countSort(arr);

printArray(arr);

return 0;

}

Back | FazBrowse Home | New Git URL