Python Coding Test Course, Card Sorting

Algorithm problem-solving skills are an important factor in technical interviews. In this post, we will deal with the algorithm problem called ‘Card Sorting’ and examine the problem-solving process step by step. This problem is one of the types frequently appearing in actual coding tests and involves sorting the given cards in a specific way. Through this article, let’s enhance our understanding of the problem and learn methods that can be applied in practice.

Problem Definition

There are N given cards. These cards are marked with numbers, which are integers. Our goal is to sort these cards. However, we must follow specific rules during this process.

Function Signature:
def card_sorting(cards: List[int]) -> List[int]:
    pass

Here, cards is a list of integers and we need to return the sorted cards. However, each card must be sorted in a predetermined manner. It is important to note that there may be specific conditions related to performing the card sorting, and these conditions must be handled effectively.

Approach to the Problem

Now, let’s look at the approach to solve the problem. Let’s assume there are the following detailed rules for the card sorting problem:

  • The cards are arranged in the given order, and each card is sorted by comparing it with adjacent cards.
  • During the sorting process, cards with smaller numbers are moved to the left.
  • The numbers on each card are unique and not duplicated.

Now, we can use various algorithms to sort the cards. The commonly used algorithms are as follows:

  • Bubble Sort
  • Selection Sort
  • Insertion Sort
  • Quick Sort
  • Merge Sort

A theoretical explanation is also needed for each algorithm, so I will provide a brief description for each of them.

Bubble Sort

Bubble Sort is one of the simplest sorting algorithms. This algorithm sorts by comparing two adjacent elements. It repeats the process for the size of the list, comparing adjacent elements and swapping them as needed. In the worst case, it has a time complexity of O(N²).

Selection Sort

Selection Sort finds the smallest value from the given list and continues sorting from there. It repeats the process for the size of the list, finding the smallest value from the remaining elements and placing it in the current position. This also has a time complexity of O(N²).

Insertion Sort

Insertion Sort inserts new elements into already sorted data. Initially, the first element is considered sorted, and from the next element, it is inserted in the sorted position. Generally, it has a time complexity of O(N²), but it performs better when the data is nearly sorted.

Quick Sort

Quick Sort is based on a divide-and-conquer algorithm and selects a pivot element to partition the list into values smaller and larger than the pivot. After that, it recursively applies Quick Sort to each sublist. On average, it has a time complexity of O(N log N).

Merge Sort

Merge Sort also uses the divide-and-conquer technique. It splits the list in half, recursively sorts each list, and then merges the two sorted lists. It also has a time complexity of O(N log N).

Solution – Implementing Card Sorting

Now, let’s implement the Python code to solve the card sorting problem. We will use Quick Sort to tackle this problem.

from typing import List

def quick_sort(cards: List[int]) -> List[int]:
    if len(cards) <= 1:
        return cards
    pivot = cards[len(cards) // 2]
    left = [x for x in cards if x < pivot]
    middle = [x for x in cards if x == pivot]
    right = [x for x in cards if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

def card_sorting(cards: List[int]) -> List[int]:
    return quick_sort(cards)

Test Cases

Now that the code is implemented, let’s check if it works correctly with various test cases.

if __name__ == "__main__":
    test_cases = [
        [3, 6, 8, 10, 1, 2, 1],
        [5, 2, 9, 1, 5, 6],
        [2, 7, 1, 8, 2, 3, 5]
    ]
    
    for cards in test_cases:
        sorted_cards = card_sorting(cards)
        print(f"Original: {cards} -> Sorted: {sorted_cards}")

When you run this code, you can get results like the following:

Original: [3, 6, 8, 10, 1, 2, 1] -> Sorted: [1, 1, 2, 3, 6, 8, 10]
Original: [5, 2, 9, 1, 5, 6] -> Sorted: [1, 2, 5, 5, 6, 9]
Original: [2, 7, 1, 8, 2, 3, 5] -> Sorted: [1, 2, 2, 3, 5, 7, 8]

Conclusion

In this article, we explored various sorting algorithms to solve the ‘Card Sorting’ problem, using the Quick Sort algorithm to arrive at a solution. The implementation method using Python, along with appropriate test cases, verified the accuracy of the code. Through problems like this, I hope to cultivate algorithmic thinking and achieve good results in coding tests. Keep practicing with various problems and enhance your skills!