Giudoku Official Site
Selection sort

Selection sort is an interesting method of sorting, with a complexity of Theta(n²).

It works like this: you pick up the minimum element in the array and exchange it with the first element. Then you repeat this for the subarray of n-1 dimension (n is the length of the original array).
You go on with this method until you obtain a subarray formed by just one element, and you can stop the algorithm.
An interesting note: the complexity of this algorithm only depends on the array dimension, not on the "degree" of sorting. In fact you can note almost the same amount of operations either for a sorted array and for a random one.

Here I will present an iterative and a recursive implementation, both written in C.
Note: as you can note, getMinimumElementIndex isn't recursive, even if I already had a recursive function (you can find it in the menu). I chose to do that in order not to "weight" too much the whole thing.

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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10
#define MAXVALUE 20

void printArray(int []);
void selectionSort(int []);
int getMinimumElementIndex(int[], int);
void swap(int[], int, int);

int main(int argc, char *argv[])
{
	int v[SIZE];
	int i;
	
	/* Introducing a bit of random, just to make things more interesting */
	srand(time(NULL));
	
	for (i = 0; i < SIZE; i++)
	{
		v[i] = rand() % MAXVALUE;
	}
	
	printf("Current array is: ");
	printArray(v);
	selectionSort(v);
	printf("After sorting: ");
	printArray(v);

	return 0;
}

void printArray(int v[])
{
	int i;
	
	for (i = 0; i < SIZE; i++)
	{
		printf("%d, ", v[i]);
	}
	printf("\n");
}

/*
 * The iterative implementation
 * (which makes more clear the matter of the complexity, I think)
 */
void selectionSort(int V[])
{
	int restDim = 0;
	int i;
	
	for (restDim = 0; restDim < SIZE; restDim++)
	{
		for (i = restDim; i < SIZE; i++)
		{
			int minPos = getMinimumElementIndex(V, restDim);
			if (V[minPos] < V[restDim])
			{
				swap(V, minPos, restDim);
			}
		}
	}
}

int getMinimumElementIndex(int v[], int startingIndex)
{
	int i;
	int minIndex = startingIndex;
	
	for (i = startingIndex+1; i < SIZE; i++)
	{
		if (v[i] < v[minIndex])
		{
			minIndex = i;
		}
	}
	
	return minIndex;
}

/*
 * I discovered by casualty this curious method for swapping the content of
 * two variables without using a third temporary variable.
 * I don't know why it works, but, whatever, it's funny.
 * For those with little memory, ^ is the binary XOR (exclusive OR) operator.
 */
void swap(int v[], int index1, int index2)
{
	v[index1] ^= v[index2];
	v[index2] ^= v[index1];
	v[index1] ^= v[index2];
}


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
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define SIZE 10
#define MAXVALUE 20

void printArray(int []);
void recursiveSelectionSort(int [], int);
int getMinimumElement(int [], int);
void swap(int[], int, int);

int main(int argc, char *argv[])
{
	int v[SIZE];
	int i;
	
	srand(time(NULL));

	for (i = 0; i < SIZE; i++)
	{
		v[i] = rand() % MAXVALUE;
	}
	
	
	printf("Current array is: ");
	printArray(v);
	recursiveSelectionSort(v, 0);
	printf("After sorting: ");
	printArray(v);

	return 0;
}

void printArray(int v[])
{
	int i;
	
	for (i = 0; i < SIZE; i++)
	{
		printf("%d, ", v[i]);
	}
	printf("\n");
}

/*
 * The recursive version
 * Very easy to understand, since the definition of selection sort
 * already gives you lots of hints about the recursive call!
 */
void recursiveSelectionSort(int v[], int restDim)
{
	int minPos;
	
	if (restDim < SIZE)
	{
		minPos = getMinimumElementIndex(v, restDim);
		
		if (v[minPos] < v[restDim])
		{
			swap(v, minPos, restDim);
		}
		
		recursiveSelectionSort(v, restDim + 1);
	}
}

int getMinimumElementIndex(int v[], int startingIndex)
{
	int i;
	int minIndex = startingIndex;
	
	for (i = startingIndex+1; i < SIZE; i++)
	{
		if (v[i] < v[minIndex])
		{
			minIndex = i;
		}
	}
	
	return minIndex;
}

void swap(int v[], int index1, int index2)
{
	v[index1] ^= v[index2];
	v[index2] ^= v[index1];
	v[index1] ^= v[index2];
}