Cách so sánh hai phần tử liền kề trong danh sách bằng Python

Một mảng inArr chứa n số (dương hoặc âm) được đưa ra. Nhiệm vụ là trả về mảng sau khi sắp xếp lại các phần tử của các số nguyên sao cho không có 2 phần tử liền kề nào bằng nhau. Nếu có nhiều cách sắp xếp hợp lệ, thì bất kỳ cách sắp xếp hợp lệ nào cũng có thể được trả lại. Nếu mảng đầu vào không chứa bất kỳ sự sắp xếp hợp lệ nào, thì một thông báo thích hợp có thể được hiển thị trên bảng điều khiển

ví dụ 1

Đầu vào

int inArr[] = {7, 7, 6, 8}

đầu ra. {7, 6, 7, 8}

Giải trình. Có nhiều cách sắp xếp hợp lệ có thể. Những sắp xếp hợp lệ được đề cập dưới đây. {7, 6, 7, 8}, {7, 6, 8, 7}, {7, 8, 7, 6}, {7, 8, 6, 7}, {8, 7, 6, 7}, . Trong đó {7, 6, 7, 8} được đề cập trong đầu ra

ví dụ 2

Đầu vào

int inArr[] = {2, 4, 8, 9, 5, 7, 3, 6, 1}

đầu ra. {2, 4, 8, 9, 5, 7, 3, 6, 1}

Giải trình. Mảng đầu vào được đưa ra theo cách không có hai phần tử nào có cùng giá trị. Do đó, các mảng đầu vào chính là câu trả lời

ví dụ 3

Đầu vào

mảng int[] = {3, 3, 3, 3, 3}

đầu ra. không thể sắp xếp hợp lệ khi các phần tử liền kề có giá trị khác nhau

Giải trình. Tất cả các phần tử có cùng giá trị. Do đó, không có sự sắp xếp hợp lệ là có thể

Tiếp cận. Lực lượng vũ phu

Theo cách tiếp cận này, chúng tôi tính toán tất cả các sắp xếp của mảng đầu vào. Nếu có bất kỳ thỏa thuận hợp lệ nào, chúng tôi sẽ trả lại thỏa thuận đó. Nếu không thể sắp xếp hợp lệ, hãy hiển thị thông báo thích hợp

Để tính được cách sắp xếp hợp lệ, đầu tiên, chúng ta sẽ sắp xếp mảng theo thứ tự tăng dần. Sau đó ta sẽ tìm hoán vị tiếp theo của mảng đã sắp và kiểm tra xem đó có phải là một cách sắp xếp hợp lệ hay không. Nếu đó là một sự sắp xếp hợp lệ, thì chúng ta có thể trả lại sự sắp xếp đó. Nếu không ta sẽ tìm hoán vị tiếp theo và cứ tiếp tục như vậy cho đến khi tìm được cách sắp xếp hợp lệ hoặc hết các cách sắp xếp. Nếu các cách sắp xếp đã hết, thì chúng ta có thể nói rằng không có cách sắp xếp hợp lệ nào cho mảng đầu vào đã cho và điều tương tự được minh họa trong chương trình sau

Tên tệp. Điều chỉnh duy nhất. java

đầu ra

For the input array: 
7 7 6 8 
The valid arrangement is: 
6 7 8 7 

For the input array: 
2 4 8 9 5 7 3 6 1 
The valid arrangement is: 
2 4 8 9 5 7 3 6 1 

For the input array: 
3 3 3 3 3 
The valid arrangement is not possible.

Phân tích độ phức tạp. Vì chương trình đang sử dụng sắp xếp nên độ phức tạp về thời gian của chương trình là O(N * log(N)). Chương trình sử dụng một tập hợp để lưu trữ các phần tử và số lần xuất hiện của chúng. Chương trình cũng đang sử dụng một mảng phụ trợ (arr). Do đó, làm cho độ phức tạp không gian của chương trình là (N), trong đó N là tổng số phần tử có trong mảng đầu vào

Sắp xếp bong bóng là một thuật toán sắp xếp so sánh hai phần tử liền kề và hoán đổi chúng cho đến khi chúng theo thứ tự dự định

Giống như sự chuyển động của bong bóng khí trong nước nổi lên mặt nước, mỗi phần tử của mảng sẽ di chuyển đến cuối mỗi lần lặp. Do đó, nó được gọi là sắp xếp bong bóng

Hoạt động của Sắp xếp bong bóng

Giả sử chúng ta đang cố sắp xếp các phần tử theo thứ tự tăng dần

1. Lần lặp đầu tiên (So sánh và Hoán đổi)

1. Bắt đầu từ chỉ mục đầu tiên, so sánh các yếu tố đầu tiên và thứ hai
2. Nếu phần tử đầu tiên lớn hơn phần tử thứ hai, chúng được đổi chỗ
3. Bây giờ, so sánh các yếu tố thứ hai và thứ ba. Trao đổi chúng nếu chúng không theo thứ tự
4. Quá trình trên cứ tiếp tục cho đến phần tử cuối cùng.
   So sánh các phần tử liền kề

2. Vòng lặp còn lại

Quá trình tương tự diễn ra cho các lần lặp còn lại

Sau mỗi lần lặp, phần tử lớn nhất trong số các phần tử chưa sắp xếp được đặt ở cuối

Trong mỗi lần lặp, việc so sánh diễn ra cho đến phần tử chưa sắp xếp cuối cùng

Mảng được sắp xếp khi tất cả các phần tử chưa sắp xếp được đặt vào đúng vị trí của chúng

Thuật toán sắp xếp bong bóng

bubbleSort(array)
  for i <- 1 to indexOfLastUnsortedElement-1
    if leftElement > rightElement
      swap leftElement and rightElement
end bubbleSort

Mã sắp xếp bong bóng trong Python, Java và C/C++

# Bubble sort in Python

def bubbleSort(array):
    
  # loop to access each array element
  for i in range(len(array)):

    # loop to compare array elements
    for j in range(0, len(array) - i - 1):

      # compare two adjacent elements
      # change > to < to sort in descending order
      if array[j] > array[j + 1]:

        # swapping elements if elements
        # are not in the intended order
        temp = array[j]
        array[j] = array[j+1]
        array[j+1] = temp


data = [-2, 45, 0, 11, -9]

bubbleSort(data)

print('Sorted Array in Ascending Order:')
print(data)

// Bubble sort in Java

import java.util.Arrays;

class Main {

  // perform the bubble sort
  static void bubbleSort(int array[]) {
    int size = array.length;
    
    // loop to access each array element
    for (int i = 0; i < size - 1; i++)
    
      // loop to compare array elements
      for (int j = 0; j < size - i - 1; j++)

        // compare two adjacent elements
        // change > to < to sort in descending order
        if (array[j] > array[j + 1]) {

          // swapping occurs if elements
          // are not in the intended order
          int temp = array[j];
          array[j] = array[j + 1];
          array[j + 1] = temp;
        }
  }

  public static void main(String args[]) {
      
    int[] data = { -2, 45, 0, 11, -9 };
    
    // call method using class name
    Main.bubbleSort(data);
    
    System.out.println("Sorted Array in Ascending Order:");
    System.out.println(Arrays.toString(data));
  }
}

// Bubble sort in C

#include 

// perform the bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size - 1; ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - step - 1; ++i) {
      
      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {
        
        // swapping occurs if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    printf("%d  ", array[i]);
  }
  printf("\n");
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find the array's length
  int size = sizeof(data) / sizeof(data[0]);

  bubbleSort(data, size);
  
  printf("Sorted Array in Ascending Order:\n");
  printArray(data, size);
}

// Bubble sort in C++

#include 
using namespace std;

// perform bubble sort
void bubbleSort(int array[], int size) {

  // loop to access each array element
  for (int step = 0; step < size; ++step) {
      
    // loop to compare array elements
    for (int i = 0; i < size - step; ++i) {

      // compare two adjacent elements
      // change > to < to sort in descending order
      if (array[i] > array[i + 1]) {

        // swapping elements if elements
        // are not in the intended order
        int temp = array[i];
        array[i] = array[i + 1];
        array[i + 1] = temp;
      }
    }
  }
}

// print array
void printArray(int array[], int size) {
  for (int i = 0; i < size; ++i) {
    cout << "  " << array[i];
  }
  cout << "\n";
}

int main() {
  int data[] = {-2, 45, 0, 11, -9};
  
  // find array's length
  int size = sizeof(data) / sizeof(data[0]);
  
  bubbleSort(data, size);
  
  cout << "Sorted Array in Ascending Order:\n";  
  printArray(data, size);
}

Thuật toán sắp xếp bong bóng được tối ưu hóa

Trong thuật toán trên, tất cả các so sánh được thực hiện ngay cả khi mảng đã được sắp xếp

Điều này làm tăng thời gian thực hiện

Để giải quyết vấn đề này, chúng ta có thể giới thiệu một biến bổ sung được hoán đổi. Giá trị của hoán đổi được đặt thành true nếu xảy ra hoán đổi các phần tử. Mặt khác, nó được đặt sai

Sau một lần lặp, nếu không có hoán đổi, giá trị của hoán đổi sẽ là sai. Điều này có nghĩa là các phần tử đã được sắp xếp và không cần thực hiện thêm bước lặp nào nữa

Làm cách nào để so sánh hai phần tử liên tiếp trong danh sách bằng Python?

Làm cách nào để so sánh phần tử đầu tiên với phần tử tiếp theo của danh sách trong Python?