C++

Forum

 
Best way to sort an array

zoran404 (263)
This is the best idea og algorithm for sorting an array that I could come up with.
But I read on internet that there are many other ways of strting an array, but didn't found how the algorithms work. So if you know a better or just different way of sorting an array please post.
1
2
3
4
5
6
7
8
9
10
11
12
 
void mySort(int a[], unsigned n)
{
    for(unsigned k = n-1, x = 0; x!=k; x++)
        for(unsigned m = x, y = x+1; y!=n; y++)
            if(a[x] > a[y]) m = i;
            if(m != n)
            {
                int h = a[x];
                a[x] = a[m];
                a[m] = h;
            }
}
Cubbi (4774)
C++ knows how to sort arrays already, no need to write anything special:
1
2
3
4
 
void mySort(int a[], unsigned n)
{
    std::sort(a, a+n);
}
eklavya sharma 2 (170)
Cubbi's solution's best if you are writing code whose main purpose is not sorting. However, if you want to write a sorting algorithm for your own practice, there are many more algorithms much faster than yours.

How fast an algorithm is measured by the big O notation. The algorithm you have written is called Selection Sort. It's speed is O(n^2), i.e. time taken is proportional to square of size of array.

The easiest algorithms have speed O(n^2) while a bit difficult but faster ones have speed O(n*log n).

List of some easy sorting algorithms (you can get their working on wikipedia):
Bubble sort O(n^2) http://en.wikipedia.org/wiki/Bubble_sort
Insertion sort O(n^2)
Merge sort O(nlogn)
zoran404 (263)
Ok, so I finaly decided to write functions for sorting an array.
I have wrote the functions for sorting then the number of calculated arithmetic, logical and comparision operations and asignments for a givven array (and displayed it) and got to a conclusion that they are all about the same speed.
But when i got to merge sort I got a bit confused by the animation on wikipedia http://upload.wikimedia.org/wikipedia/commons/c/cc/Merge-sort-example-300px.gif
It shows how it is done with array of lenght of 8, but what if it can not be devaded by 2? What if it is 3, 7, 12?

Take a look of what I wrote:
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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
 
#include <iostream>
#include <cstdlib>

using std::cout;
using std::cin;

void copy(int* a, int n);
void selectionSort(int* a, int n);
void doubleSort(int* a, int n);
void insertionSort(int* a, int n);
void mergeSort(int* a, int n);

main()
{
    int n;
    do {
        cout << "Koliko elemenata? ";
        cin >> n;
    } while (n<2);
    
    int *a = new int[n], *s = new int[n];
    if(n>4) cout << "Unesite " << n << " celih brojeva:\n";
    else cout << "Unesite " << n << " cela broja:\n";
    for(int x = 0; x!=n; x++) cin >> a[x];
    
    cout<<'\n';
    for(int x = 0; x<n; x++) s[x] = a[x];
    selectionSort(s,n);
    for(int x = 0; x<n; x++) s[x] = a[x];
    doubleSort(s,n);
    for(int x = 0; x<n; x++) s[x] = a[x];
    insertionSort(s,n);
    
    delete a;
    delete s;
    
    cin.get();cin.get();
    return 0;
}

void selectionSort(int* a, int n)
{
    int b = 4;
    for(int k = n-1, x=0, m; x<k; x++)
    {
        b += 6;
        m = x;
        for(int y = x+1; y<n; y++)
        {
            b += 4;
            if(a[m] > a[y]) { m = y; b++; }
        }
        if(x != m)
        {
            int h = a[x];
            a[x] = a[m];
            a[m] = h;
            b += 3;
        }
    }
    for(int x = 0; x!=n; x++) cout << a[x] << " ";
    cout << "\nZa sortiranje ovog niza Selection Sort algoritmom uradjeno je "
    << b << " operacija.\n\n";
}

void doubleSort(int* a, int n)
{
    int b = 3;
    for(int x = n-1; x>1; x--)
    {
        b += 4;
        for(int y = 1; y <= x; y++)
        {
            b += 5;
            int u = y-1;
            if(a[y] < a[u])
            {
                int h = a[y];
                a[y] = a[u];
                a[u] = h;
                b += 3;
            }
        }
    }
    for(int x = 0; x!=n; x++) cout << a[x] << " ";
    cout << "\nZa sortiranje ovog niza Double Sort algoritmom uradjeno je "
    << b << " operacija.\n\n";
}

void insertionSort(int* a, int n)
{
    int b = 2;
    for(int m, x = 1; x<n; x++)
    {
        b += 2;
        m = a[x];
        for(int y = x; ; y--)
        {
            b += 4;
            if (y==0 || a[y-1] <= m) { a[y] = m; break; b++; }
            else { a[y] = a[y-1]; b += 2; }
        }
    }
    for(int x = 0; x!=n; x++) cout << a[x] << " ";
    cout << "\nZa sortiranje ovog niza Insertion Sort algoritmom uradjeno je "
    << b << " operacija.\n\n";
}

void mergeSort(int* a, int n)
{
    
}
Last edited on
eklavya sharma 2 (170)
The animation didn't seem confusing to me. It might seem confusing to you if you don't know what merging is.

This is the first time I'm writing code for merge sort.
There is a problem: I need extra memory. I can't use new as this will slow down the algorithm. Hence, I'm using templates to tackle the problem.

http://www.cplusplus.com/doc/tutorial/templates/
(in case you don't know what templates are)

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
43
44
45
46
47
48
49
50
 
#include<iostream>
using namespace std;

void merge(int* a,int na,int* b,int nb,int* c)
{
	int pa=0,pb=0,pc=0;
	while(pa<na && pb<nb)
	{
		if(a[pa]<=b[pb])c[pc++]=a[pa++];
		else c[pc++]=b[pb++];
	}
	while(pa<na)c[pc++]=a[pa++];
	while(pb<nb)c[pc++]=b[pb++];
}

template<int n>
void mergesort(int* a)
{
	const int k=n/2;
	int *b,c[n],i;
	b=a+k;
	mergesort<k>(a);
	mergesort<n-k>(b);
	merge(a,k,b,n-k,c);
	for(i=0;i<n;i++)a[i]=c[i];
}

template<>
void mergesort<1>(int* a){}

template<>
void mergesort<2>(int* a)
{
	int t;
	if(a[0]>a[1])
	{t=a[0];a[0]=a[1];a[1]=t;}
}

int main()
{
	const int n=8;
	int i,a[n];
	for(i=0;i<n;i++)
	{
		cout<<"Enter "<<i+1<<"th no ";
		cin>>a[i];
	}
	mergesort<n>(a);
	for(i=0;i<n;i++)cout<<a[i]<<endl;
}


I've tested this code and it runs.
The problem was easy but not as easy as I thought.

There's a probablity that you don't know what templates are and I should've used new. But finding new related bugs is harder and I'm more comfortable with templates and I am feeling very sleeeeeeeeeeeepy. Good night.
Last edited on
zoran404 (263)
That still sorts 8 elements...
eklavya sharma 2 (170)
change the value of n (in main) to whatever you like.
zoran404 (263)
So, I looked at your code and I think I get it, but I have a problem.
Apparently standard only allows constant value to be passed for template when calling mergesort<n>(a);
How do I first input value for n then pass it to the template?
eklavya sharma 2 (170)
Well you can do that in my example by dynamically allocating arrays and taking n as a parameter instead of a template parameter. I think that this approach will make the sorting process slower as dynamic allocation and deallocation take a lot of time.

There are more than one ways to merge 2 sorted arrays into a single sorted array. The way I have used for merging is not really fit for this purpose. I presently don't know other ways to do this.
zoran404 (263)
Ok, I'll use if else instead of template...
Topic archived. No new replies allowed.