Đếm mã Python sắp xếp

Sắp xếp đếm là phương pháp sắp xếp theo thời gian tuyến tính để sắp xếp các mục trong một mảng. Trong hướng dẫn này, chúng ta sẽ sắp xếp một mảng với sự trợ giúp của thao tác sắp xếp đếm

Sắp xếp đếm - Giới thiệu cơ bản

Sắp xếp đếm là một thuật toán sắp xếp sắp xếp các phần tử của mảng bằng cách đếm số lần mỗi phần tử duy nhất xuất hiện trong mảng. Số đếm được lưu trong một mảng phụ trợ và việc sắp xếp được thực hiện bằng cách ánh xạ số đếm tới một chỉ mục mảng phụ trợ. Nó hoạt động bằng cách xác định số lượng mục có giá trị khóa duy nhất (loại băm). Bây giờ chúng ta hãy hiểu sơ bộ về cách sắp xếp đếm được thực hiện

1. Tìm phần tử tối đa từ một mảng nhất định
2. Khởi tạo độ dài mảng với tất cả các phần tử 0. Điều này sẽ được sử dụng để sắp xếp các phần tử đếm
3. Số lượng cửa hàng của từng phần tử đối với chỉ mục của chúng
4. Theo dõi tổng số các mục của mảng đếm
5. Trong mảng đếm, lấy chỉ số của từng phần tử trong mảng ban đầu. Điều này cho bạn biết tổng số mục. Đặt phần tử tại chỉ mục được tính toán, như được chỉ ra trong sơ đồ bên dưới
6. Sau khi hoàn thành tất cả các bước này, hãy giảm số đếm xuống 1
7. Mảng kết quả sẽ được sắp xếp một

thuật toán

Đến bây giờ, chúng ta đã hiểu sơ bộ về cách thực hiện sắp xếp đếm. Để hiểu rõ hơn, hãy đi sâu vào thuật toán, sau đó là mã

1. Định nghĩa hàm Counting_Sort()
2. Truyền tham số mảng cho hàm
3. Khởi tạo mảng đếm
4. Lưu trữ số lượng của từng phần tử trong mảng đếm
5. Tìm chỉ số của từng phần tử trong mảng ban đầu
6. Đặt phần tử vào mảng đếm
7. Sao chép phần tử đã sắp xếp trong mảng đếm
8. Mảng được sắp xếp ngay bây giờ
9. In mảng kết quả

Chương trình đếm Sort(Array)

Như đã thảo luận ở trên về thuật toán, bây giờ chúng ta hãy đi sâu vào phần lập trình của thao tác Sắp xếp đếm chịu ảnh hưởng của thuật toán

def Counting_Sort(arr):
    s = len(arr)
    result = [0] * s

    # count array
    count = [0] * 10
    
    for i in range(0, s):
        count[arr[i]] += 1
        
    # cummulative count
    for i in range(1, 10):
        count[i] += count[i - 1]

    # place the elements in output array
    i = s - 1
    while i >= 0:
        result[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1
        i -= 1

    # Copy sorted elements 
    for i in range(0, s):
        arr[i] = result[i]

#driver code
array = [9, 8, 4, 5, 8, 9, 3, 2, 3, 1]
print("The original array is: ", array)
Counting_Sort(array)
print("Array after sorting is: ", array)

Mảng ban đầu là. [9, 8, 4, 5, 8, 9, 3, 2, 3, 1]
Mảng sau khi sắp xếp là. [1, 2, 3, 3, 4, 5, 8, 8, 9, 9]

Chương trình đếm Sắp xếp (Ký tự)

Vì chúng tôi đã sắp xếp một mảng, chúng tôi cũng có thể sắp xếp các ký tự với sự trợ giúp của sắp xếp đếm

def Counting_Sort(array):

	result = [0 for a in range(len(array))]

	count = [0 for a in range(256)]

	# string is immutable
	answer = ["" for _ in array]

	# Store count
	for a in array:
		count[ord(a)] += 1

	for a in range(256):
		count[a] += count[a-1]

	# output character array
	for a in range(len(array)):
		result[count[ord(array[a])]-1] = array[a]
		count[ord(array[a])] -= 1

	# Copy the output array 
	for a in range(len(array)):
		answer[a] = result[a]
	return answer

# Driver program 
array = "shubhsinha"
print("The original array is:", array)
ans = Counting_Sort(array)
print("Character array after sorting is % s" %("".join(ans)))

Mảng ban đầu là. shubhsinha
Mảng ký tự sau khi sắp xếp là abhhhinssu

Phần kết luận

Trong hướng dẫn này, chúng tôi đã thực hiện thao tác Sắp xếp Đếm trong python để sắp xếp một mảng. Sắp xếp đếm được sử dụng khi có nhiều số nguyên nhỏ hơn với nhiều lần đếm. Độ phức tạp trường hợp tốt nhất của sắp xếp bong bóng là O(n+k) và độ phức tạp không gian của sắp xếp bong bóng là O(max)

Sắp xếp đếm trong python được sử dụng để sắp xếp mảng bằng cách đếm số lần xuất hiện của từng mục duy nhất trong mảng. Python cũng cung cấp các phương thức có sẵn để sắp xếp mảng. Sắp xếp đếm là một loại thuật toán sắp xếp, trong đó thuật toán này hoạt động bằng cách đếm số lần xuất hiện của các phần tử duy nhất trong mảng và tìm vị trí của từng phần tử trong mảng bằng cách thực hiện phép tính số học trên các lần đếm đó. Số lượng được lưu trong một mảng phụ trợ và việc sắp xếp được thực hiện bằng cách ánh xạ số lượng dưới dạng chỉ mục của mảng phụ trợ. Thời gian chạy của sắp xếp đếm là tuyến tính O(n)

Gói phát triển phần mềm tất cả trong một(hơn 600 khóa học, hơn 50 dự án)

Giá
Xem khóa học

600+ Khóa học trực tuyến. hơn 50 dự án. Hơn 3000 giờ. Giấy chứng nhận có thể kiểm chứng. Truy cập Trọn đời
4. 6 (84.533 xếp hạng)

Thuật toán sắp xếp đếm

Thuật toán sắp xếp đếm được đưa ra dưới đây

Bắt đầu khóa học phát triển phần mềm miễn phí của bạn

Phát triển web, ngôn ngữ lập trình, kiểm thử phần mềm và những thứ khác

Counting_Sort( a )
  maxele <- maximum element in a
  for i <- 0 to len(a)
    In count array store the total count of each unique element at an ith index 
  for i <- 1 to maxele
    In count array store the cumulative sum 
  for j <- len(a) down to 1
    copy the elements to array
    decrement the count of each copied element by 1

Giá trị trả về

Giá trị trả về của phương thức này là mảng đã được sắp xếp

Làm việc về sắp xếp đếm trong Python

Đưa ra dưới đây là hoạt động của sắp xếp đếm trong python

1. Đầu tiên, xác định phần tử lớn nhất trong mảng được chỉ định là max

mảng đã cho. [3, 1, 1, 7, 2, 2, 0], tối đa=7

2. Tạo một mảng với tất cả các phần tử 0 và độ dài tối đa + 1. Danh sách này được sử dụng để theo dõi số phần tử trong mảng

Đếm mảng. [0, 0, 0, 0, 0, 0, 0, 0]

3. Trong danh sách đếm, lưu trữ số đếm của từng biến tại chỉ mục tương ứng của nó

Xét ví dụ phần tử 2 có số đếm là 2 thì 2 được lưu ở vị trí thứ 2 của mảng đếm. Nếu phần tử “6” không có trong mảng thì 0 được lưu ở vị trí thứ 6

Số lượng từng phần tử được lưu trữ. [1, 2, 2, 1, 0, 0, 0, 1]

4. Lưu tổng số phần tử của mảng đếm. Nó hỗ trợ sắp xếp các phần tử trong chỉ mục bên phải của mảng được sắp xếp

số lượng tích lũy. [1, 3, 5, 6, 6, 6, 6, 6, 7]

5. Trong mảng đếm, tìm chỉ mục của từng thành viên của mảng ban đầu. Điều này cung cấp cho bạn tổng số sản phẩm. Đặt phần tử tại chỉ mục được tính toán. Sau khi mỗi phần tử đã được đặt vào đúng vị trí của nó, hãy giảm số lượng của nó xuống một

sắp xếp đếm. [0, 1, 1, 2, 2, 3, 7]

Ví dụ về Python sắp xếp đếm

Các ví dụ khác nhau được đề cập dưới đây

Ví dụ 1

Ví dụ sắp xếp đếm trong python để sắp xếp mảng số

Mã số

def counting_Sort(ary):
  size = len(ary)
  output = [0] * size
  # create and initialize count array
  count = [0] * 10
  # In the count array, keep track of how many of each variable there are.
  for no in range(0, size):
      count[ary[no]] += 1
  # Keep track of the total number of count
  for no in range(1, 10):
      count[no] += count[no - 1]
  # In the count array, find the index of each member of the original array.
  # and place the elements in output array
  no = size - 1
  while no >= 0:
    output[count[ary[no]] - 1] = ary[no]
    count[ary[no]] -= 1
    no -= 1
  # Copy the sorted elements into original array
  for no in range(0, size):
      ary[no] = output[no]
data = [ 4, 2, 4, 1, 3, 7, 9 ]
print( "The given array is: " )
print( data )
counting_Sort( data )
print( "The sorted array in ascending Order is: " )
print(data)

đầu ra

Như trong chương trình trên, mảng đầu ra (lưu trữ 0 của kích thước mảng) và mảng đếm (lưu trữ 0 của kích thước 10) được tạo. Tiếp theo trong mảng đếm, hãy theo dõi xem có bao nhiêu biến ở đó và lưu trữ số đếm tích lũy. Tiếp theo, xác định chỉ số của từng số của mảng ban đầu trong mảng đếm và đặt chúng vào mảng đầu ra. Sau đó, cuối cùng, sao chép mảng đầu ra là mảng đã sắp xếp sang mảng đã truyền để in, như chúng ta có thể thấy trong đầu ra ở trên

Ví dụ #2

Ví dụ đếm sort trong python để sắp xếp mảng ký tự

Mã số

def counting_Sort(ary):
    size = len(ary)
    output = [0] * size
    # create and initialize with 0 the count array to store
    # count of each characters 
    count = [0 for no in range(256)]
    # In the count array, keep track of how many of each variable there are.
    for no in ary:
        count[ord(no)] += 1
    # Keep track of the total number of count
    for no in range(256):
        count[no] += count[no - 1]
    # In the count array, find the index of each character of the original array.
    #  and place the elements in output array
    no = size - 1
    while no >= 0:
        output[count[ord(ary[no])] - 1] = ary[no]
        count[ord(ary[no])] -= 1
        no -= 1
    # Copy the sorted elements into original array
    for no in range(0, size):
        ary[no] = output[no]
data = [ 'a', 'f', 't', 'w' ]
print( "The given array is: " )
print( data )
counting_Sort( data )
print( "The sorted array in ascending Order is: " )
print( data )

đầu ra

Như trong chương trình trên, mảng đầu ra (lưu trữ 0 của kích thước mảng) và mảng đếm (lưu trữ 0 của kích thước 256) được tạo. Tiếp theo trong mảng đếm, hãy theo dõi xem có bao nhiêu ký tự trong mỗi ký tự và lưu số đếm tích lũy với sự trợ giúp của hàm ord(), hàm này trả về biểu diễn số nguyên của ký tự đã chỉ định. Tiếp theo, xác định chỉ số của từng ký tự của mảng ban đầu trong mảng đếm và đặt chúng vào mảng đầu ra. Sau đó, cuối cùng, sao chép mảng đầu ra là mảng đã sắp xếp sang mảng đã truyền để in, như chúng ta có thể thấy trong đầu ra ở trên

Ví dụ #3

Ví dụ đếm sắp xếp trong python để sắp xếp các ký tự trong chuỗi đã cho

Mã số

def counting_Sort(ary):
    size = len(ary)
    output = [0] * size
    # create and initialize with 0 the count array to store
    # count od each characters 
    count = [0 for i in range(256)]
    # In the count array, keep track of how many of each variable there are.
    for no in ary:
        count[ord(no)] += 1
    # Keep track of the total number of count
    for no in range(256):
        count[no] += count[no - 1]
    # create the string to store the resultant string 
    str = ["" for no in ary]
    # In the count array, find the index of each character of the original array.
    #  and place the elements in output array
    no = size - 1
    while no >= 0:
        output[count[ord(ary[no])] - 1] = ary[no]
        count[ord(ary[no])] -= 1
        no -= 1
    # Copy the sorted elements into original array
    for i in range(len(ary)):
        str[i] = output[i]
    return "".join( str )
data = "hello"
print( "The given array is: " )
print( data )
data = counting_Sort( data )
print( "The sorted array in ascending Order is: " )
print( data )

đầu ra

Như trong chương trình trên, mảng đầu ra (lưu trữ 0 của kích thước mảng), mảng đếm (lưu trữ 0 của kích thước 256) và str (lưu trữ “” của kích thước mảng) được tạo. Tiếp theo trong mảng đếm, hãy theo dõi xem có bao nhiêu ký tự trong mỗi ký tự và lưu số đếm tích lũy với sự trợ giúp của hàm ord(), hàm này trả về biểu diễn số nguyên của ký tự đã chỉ định. Tiếp theo, xác định chỉ số của từng ký tự của mảng ban đầu trong mảng đếm và đặt chúng vào mảng đầu ra. Sau đó, cuối cùng, sao chép mảng đầu ra là mảng đã sắp xếp sang mảng str và nối từng ký tự của mảng với sự trợ giúp của phương thức join(), phương thức này trả về chuỗi tăng dần

Phần kết luận

Chuỗi sắp xếp trong python được sử dụng để sắp xếp mảng bằng cách đếm số lần xuất hiện của từng mục duy nhất trong mảng

Bài viết được đề xuất

Đây là hướng dẫn về Đếm sắp xếp Python. Ở đây chúng tôi thảo luận về phần giới thiệu, thuật toán và cách sắp xếp đếm trong python cùng với các ví dụ khác nhau và triển khai mã. Bạn cũng có thể xem các bài viết sau để tìm hiểu thêm –

Là sắp xếp đếm nhanh nhất?

Thuật toán của phương thức sort() trong Python là gì?

Cách nhanh nhất để sắp xếp danh sách trong Python là gì?