The Sorting Lab

Activity Description

Content

The process of arranging a set of data in a particular order is called sorting. This order can be in increasing or decreasing order, lexicographically order, alphabetical order, and so on.

Suppose you have an array of items that are not in order:

int[] a = {224,6,2,18,4,7,21,-6,3,13};

How can you order them?

Possible ideas include:

• Move the smallest to position 0 and repeat to find the second smallest

• Keep checking the smallest vs the largest.

All of those ideas include common mechanisms:

• To go over all elements

• To check/compare the magnitude

• Load a value into a position and unload a value to a different position

• Keep track of the current ordered value

In terms of code, we have:

• a loop that goes to all the values in the array

for(int i = 0; i < a.length-1; i++)

• an if-statement that checks if contagious values are in order. Noticed that we subtract 1 from the a.length because we will need to check for the next position of our current state (e.g., a[i + 1] as follows :

if(a[i] > a[i+1])

• a swap, which consists in having a temporary variable to hold the value of one position, e.g., a[i] while positioning a[i+1] takes its place, and eventually replaces the position a[i+1] by a[i].

int tmp = a[i];

  a[i] = a[i+1];

a[i+1] = tmp;

In conclusion, we have a procedure as follows:

public static void sort(int[] a){

for(int i = 0; i < a.length-1; i++){

   if(a[i] > a[i+1]){

     int tmp = a[i];

     a[i] = a[i+1];

     a[i+1] = tmp;

   }

}

  }

By running our program with the given array, we obtained the following output:

======BEFORE======

224 6 2 18 4 7 21 -6 3 13

======AFTER=======

-6 2 3 4 6 7 13 18 21 224

Notice that the largest value is indeed at its place, however, the rest of the array is not necessarily in order. If we run the algorithm 2 times consecutively

sort(a);

sort(a);

we get:                                                                                       

======BEFORE======

224 6 2 18 4 7 21 -6 3 13

======AFTER=======

-6 2 3 4 6 7 13 18 21 224

By running the program 3 times we get the 3 largest values in order; if we run it N times we got the N values. Therefore, we need an extra loop to process N times the loop, generating a transformation of the method as follows:

public static void sort(int[] a){

for(int i = 0; i < a.length-1; i++){

     for(int j = 0; j < a.length-1; j++){

       if(a[j] > a[j+1]){

              int tmp = a[j];

           a[j] = a[j+1];

              a[j+1] = tmp;

       }

    }

    }

}

We have discussed search in the past through sequential search. Related problems may include:

1. Given the following string, count how many specific characters appear in the string.

2. Given this array, return true if the target t was found in the array, false otherwise.

public static boolean sequential(int[] a, int t){

for(int i = 0; i < a.length; i++){

   if(a[i] == t)

     return true;

}

return false;

  }

The issue is that the method, in the worst-case scenario, will take n.

Related Videos

Useful Files