Swap sort is another sorting algorithm based on exchanges. Like bubble sort, swa

Question

Swap sort is another sorting algorithm based on exchanges. Like bubble sort, swap sort compares pairs of elements and swaps them when they are out of order, but swap sort looks at different pairs of elements than bubble sort does. On pass i of swap sort, the element in position i of the list is compared with the elements in all positions to the right of position i, and pairs of elements are swapped as needed. At the end of pass i, the element in position i is where it belongs in the sorted list.

For example, let's say that we have the following initial list:

                   15 8 20 5 12

On pass 0, swap sort compares the element in position 0 with the elements in positions 1 through n – 1, where n is the number of elements in the list. First, 15 is compared to 8, and because 8 is less than 15, the two elements are swapped:

                   8 15 20 5 12

Next, 8 (which is now in position 0) is compared to 20, and no swap occurs because 8 is already smaller than 20. Then 8 is compared with 5, and the two elements are swapped:

                   5 15 20  8 12

Finally, 5 is compared to 12, and no swap occurs because 5 is already smaller than 12. At this point, pass 0 is complete, and the element in position 0 (the 5) is where it belongs in the sorted list.

On pass 1, swap sort compares the element in position 1 with the elements in positions 2 through (n – 1) and performs swaps when needed. The process continues for passes 2 through (n – 2), at which point the list is fully sorted.

In the file SortCount.py, add a method called swapSort() that implements the swap sort algorithm described above. Its only parameter should be a reference to a list of integers. Like the other methods in this file, your swapSort method must make use of the compare(), and swap() helper methods so that you can keep track of the total number of comparisons and moves that it performs. If you need to compare two list elements, you should use the method call compare(comparison); for example, compare(alist[0] < alist[1]). This method will return the result of the comparison (True or False), and it will increment the count of comparisons that the class maintains. If you need to swap elements i & j of alist you should use move(alist, i, j). You also need to count the number of moves by incrementing the SortCount class variable move.

Determine the big-O time efficiency of swapSort when it is applied to two types of lists: lists that are almost sorted, and lists that are randomly ordered. You should determine the big-O expressions by experiment, rather than by analytical argument.

To do so, run the algorithm on lists of different sizes (for example, n = 1000, 2000, 4000, 8000 and 16000). Modify the test code in the main() method so that it runs swapSort on the lists that are generated, and use this test code to gather the data needed to make your comparisons. (Note: you can also test the correctness of your method by running it on lists of 10 or fewer items; the sorted list will be printed in such cases.)

For each type of list, you should perform at least ten runs for each value of n and compute the average numbers of comparisons and moves for each set of runs. Based on these results, determine the big-O efficiency class to which swapSort belongs for each type of list (O(n), O(logn), O(nlogn), O(n2), etc.). Explain clearly how you arrived at your conclusions. If the algorithm does not appear to fall neatly into one of the standard efficiency classes, explain your reasons for that conclusion, and state the two efficiency classes that it appears to fall between. Put the results of your experiments, and your accompanying analysis and conclusions, in a plain-text file called ps2_experiments.txt.USE PYTHON!!

HERE IS STARTING CODE I WAS GIVEN:

Explanation / Answer

public class SwapSort {

//static variables to count number of
//comparisions, moves and swaps
//performed by swapSort algorithm

public static int comparisions = 0;
public static int moves = 0;
public static int swaps = 0;

public static void main(String []args){
//array to be sorted
int arr[ ]={ 45, 56, 87, 15, 97, 65, 48, 35, 50, 85 };
//displaying array value before sorting
System.out.println(" Array before sorting: ");
for ( int element : arr )
System.out.print( element + " ");

//calling swapSort method to sort the array elements
swapSort ( arr ) ;
//displaying array elements after sorting
System.out.println(" After sorting using swapsort: ");
for ( int element : arr )
System.out.print( element + " ");

//displaying values of comparisions, swaps and moves
System.out.println( " Number of comparisions: " + comparisions);
System.out.println( "Number of swaps: " + swaps);
System.out.println( "Number of moves: " + moves);
}

//sorts the array elements using swapsort algorithm
public static void swapSort ( int arr[ ] ) {
for(int i = 0; i < arr.length - 1; i++)
for(int j = i+1; j < arr.length; j++)
if( compare (arr[ i ], arr[ j ] ) )
swap( arr, i, j ) ;
}

//compares its two arguments a and b
//and returns true if a greater than b
//otherwise false
public static boolean compare ( int a, int b ) {
comparisions++;
return a > b ;
}

//swaps tao array elements specified by i and j index
//variable of the array
public static void swap(int arr[ ], int i, int j ) {
int tmp = arr[ i ] ;
move ( arr, i, arr[ j ] );
move ( arr, j, tmp );
swaps++;
}

//moves the given element into the array at specified ith location
public static void move ( int arr[ ], int i, int element ) {
arr[ i ] = element;
moves++;
}
}   

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.