Question

Activity 2. Suppose you have a random sequence of black, red and white marbles and want to rearrange it such that the marbles in each color are grouped together, with the order black, white and then red. Write an algorithm using pseudocode to solve this problem. Do your best to optimize your initial solution.

Answer 1

Hi,
For this problem it is better to use Insertion Sort.
Let's discuss how insertion sort works:
It insertion sort we pick the each element from list and travel back(taking back that element) to the list upto present element is greater.
More clearly:

This is an in-place comparison-based sorting algorithm. Here, a sub-list is maintained which is always sorted. For example, the lower part of an array is maintained to be sorted. An element which is to be 'insert'ed in this sorted sub-list, has to find its appropriate place and then it has to be inserted there. Hence the name, insertion sort. The array is searched sequentially and unsorted items are moved and inserted into the sorted sub-list (in the same array).

Algorithm :

Step 1 − If it is the first element, it is already sorted. return 1;
Step 2 − Pick next element
Step 3 − Compare with all elements in the sorted sub-list
Step 4 − Shift all the elements in the sorted sub-list that is greater than the value to be sorted
Step 5 − Insert the value
Step 6 − Repeat until last element in array(list sorted)

Pseudocode :

procedure insertionSort( A : array of items )
int holePosition
int valueToInsert
for i = 1 to length(A) inclusive do:
/* select value to be inserted */
valueToInsert = A[i]
holePosition = i
/*locate hole position for the element to be inserted */
while holePosition > 0 and A[holePosition-1] > valueToInsert do:
A[holePosition] = A[holePosition-1]
holePosition = holePosition -1
end while
/* insert the number at hole position */
A[holePosition] = valueToInsert
end for
end procedure

Example:

12, 11, 13, 5, 6

Let us loop for i = 1 (second element of the array) to 4 (last element of the array)

i = 1. Since 11 is smaller than 12, move 12 and insert 11 before 12
11, 12, 13, 5, 6

i = 2. 13 will remain at its position as all elements in A[0..I-1] are smaller than 13
11, 12, 13, 5, 6

i = 3. 5 will move to the beginning and all other elements from 11 to 13 will move one position ahead of their current position.
5, 11, 12, 13, 6

i = 4. 6 will move to position after 5, and elements from 11 to 13 will move one position ahead of their current position.
5, 6, 11, 12, 13
Another example with image:

Insertion Sort Execution Example 342 10 12 1 5o 2 3 4 10 12 1 5 6 ) 1 2 3 4 10 12 6 6 1 2 3 4 5 10 26 1 2 3 4 5 6 10 12

Code:

Let assume black as 1, white as 2 and red as 3

1. Python:

# Python program for implementation of Insertion Sort
# Function to do insertion sort
def insertionSort(arr):
# Traverse through 1 to len(arr)
for i in range(1, len(arr)):
key = arr[i]
# Move elements of arr[0..i-1], that are
# greater than key, to one position ahead
# of their current position
j = i-1
while j >= 0 and key < arr[j] :
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
# Driver code to test above
arr = [2,3,1,2,2,3,2,3,2]
insertionSort(arr)
for i in range(len(arr)):
print ("% d" % arr[i])

Output: 1 2 2 2 2 2 3 3 3

2. C :

/* Function to sort an array using insertion sort*/
void insertionSort(int arr[], int n)
{
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1], that are
greater than key, to one position ahead
of their current position */
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// A utility function to print an array of size n
void printArray(int arr[], int n)
{
int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
/* Driver program to test insertion sort */
int main()
{
int arr[] = { 2, 1, 3, 3, 2, 1, 2, 2, 3};
int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;
}

Output: 1 1 2 2 2 2 3 3 3

Note:
Time complexity of insertion sort is (n is length of list):
best : n
average: n^2
worst: n^2
Space complexity is : n