Task 3: Sorting an array based list Assume you’re given a list of numbers to sor

Question

Task 3: Sorting an array based list

Assume you’re given a list of numbers to sort (in either order). Develop an algorithm to sort it.

Note: Swift also has a sort function that can be used to sort arrays.  But then again, our objective in this activty is to study sorting algorithm as we work with arrays. So we will develop our own sort function(s).

To develop an algorithm you need to be able to solve the problem manually first using some sample data.

Create a sample list to work with

Sort the sample list manually

Note: As you develop your algorithm, you need to assume that the list is very long to the point that you can’t visually scan it all at once and sort the data mentally. This is to simulate the fact that the computer can only “see” one number at a time as it re-arranges them

Once you figure out how to sort manually, trace your steps and write them down into an algorithm

Verify your algorithm with another simple example

Implement your algorithm in Swift

Test it using one of the examples you used in the steps above

Be ready to demo your algorithm and your Swift function

pls if you could write little comment for better understanding. thanks.

Explanation / Answer

the main requirement we have here is we are having a very big array of unsorted elements. Lets suppose we have array of 1,00,000 elements.

Best way to sort is quicksort as it does not takes extra memory for sorting O(nlogn). We can do sorting through merge sort also . But issue is we will require another array to store result thus increasing size.

below is algo for quicksort:--

for quicksort we need to select a pivot element (generally first item). we will put this pivot element in its correct position . After that we will get two arrays, one before the pivot element and another after it.

Use recursion to keep on selecting pivot element and partitioning array.

quickSort(arr[], low, high)

{

    if (low < high)

    {

        /* pi is partitioning index, arr[p] is now

           at right place */

        pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1); // Before pi

        quickSort(arr, pi + 1, high); // After pi

    }

}

below is partition implementation:--

partition (arr[], low, high)

{

    // pivot (Element to be placed at right position)

    pivot = arr[high];

    i = (low - 1) // Index of smaller element

    for (j = low; j <= high- 1; j++)

    {

        // If current element is smaller than or

        // equal to pivot

        if (arr[j] <= pivot)

        {

            i++;    // increment index of smaller element

            swap arr[i] and arr[j]

        }

    }

    swap arr[i + 1] and arr[high])

    return (i + 1)

}

Related Questions

Navigate

• Browse (All)
• Browse T
• Subjects

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