OCR Computer Science Sort Quiz

What is the time complexity of quicksort algorithm?

• O(n)

• O(1)

• O(n log n)

• O(n^2)

Explain the concept of stable sorting algorithm.

• Only sorts the first half of the elements

• Sorts the elements in descending order

• Randomly shuffles the elements in the sorted output

• Preserves the relative order of equal elements in the sorted output

What is the difference between comparison-based and non-comparison-based sorting algorithms?

• Comparison-based sorting algorithms use random order while non-comparison-based sorting algorithms use specific order

• Comparison-based sorting algorithms use specific order while non-comparison-based sorting algorithms use random order

• Comparison-based sorting algorithms compare elements to determine their order, while non-comparison-based sorting algorithms use other methods such as counting or distribution.

• Comparison-based sorting algorithms use counting or distribution while non-comparison-based sorting algorithms use comparison

Discuss the advantages and disadvantages of using merge sort algorithm.

• Advantages: Unstable, efficient for large datasets. Disadvantages: Requires extra space, efficient for small datasets.

• Advantages: Stable, inefficient for large datasets. Disadvantages: Requires extra space, efficient for small datasets.

• Advantages: Unstable, inefficient for large datasets. Disadvantages: Requires no extra space, efficient for small datasets.

• Advantages: Stable, efficient for large datasets. Disadvantages: Requires extra space, not as efficient for small datasets.

Explain the working principle of bubble sort algorithm.

• Bubble sort algorithm compares each pair of adjacent items and swaps them if they are in the right order.

• Bubble sort algorithm compares each pair of adjacent items and swaps them if they are in the wrong order.

• Bubble sort algorithm compares each pair of adjacent items and leaves them as they are if they are in the wrong order.

• Bubble sort algorithm compares each pair of non-adjacent items and swaps them if they are in the wrong order.

What is the best case time complexity of insertion sort algorithm?

• O(n^2)

• O(log n)

• O(n)

• O(1)

Discuss the concept of in-place sorting algorithm.

• Algorithm that sorts elements into reverse order

• Sorting algorithm that requires additional memory space

• Sorting algorithm that only works on even numbers

• Sorting algorithm that does not require extra space and sorts the elements within the given array itself

Compare and contrast selection sort and insertion sort algorithms.

• Merge sort builds the final sorted array by dividing the array into two halves and then merging them in a sorted manner

• Bubble sort repeatedly finds the maximum element from the unsorted part and puts it at the end

• Quick sort repeatedly selects a pivot element and partitions the array around the pivot

• Selection sort repeatedly finds the minimum element from the unsorted part and puts it at the beginning, while insertion sort builds the final sorted array one item at a time by taking one element from the unsorted part and inserting it into its correct position in the sorted part.

Explain the concept of external sorting in computer science.

• External sorting is a technique used to randomly access data in a computer.

• External sorting is a technique used to sort data within the main memory of a computer.

• External sorting is a technique used to compress data in a computer.

• External sorting is a technique used to sort large amounts of data that cannot fit into the main memory of a computer.

What is the significance of using radix sort algorithm in sorting large datasets?

• It has a linear time complexity

• It does not guarantee accurate sorting

• It is only suitable for small datasets

• It has an exponential time complexity